병합 정렬 (Merge Sort)
하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 분할 정복(Divide and Conquer) 알고리즘입니다.
시간 복잡도는 최선, 평균, 최악 모두 O(n log n)으로 일정하며, 안정 정렬(Stable Sort)입니다.
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(left, right) {
let result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
const arr = [38, 27, 43, 3, 9, 82, 10];
console.log("초기 배열:", arr);
console.log("정렬 결과:", mergeSort(arr));