합병 정렬이란 ?
합병 정렬은 1948년 폰 노이만이 개발한 정렬 알고리즘으로, 분할 정복(divide and conquer) 방법을 기반으로 합니다. 주어진 배열을 반으로 나누어 더 이상 나눌 수 없을 때까지 분할한 후, 작은 단위의 배열부터 합병하며 정렬해 나가는 방식입니다.
시간 복잡도
- O(n log n)
기본 동작 원리
[3, 44, 38, 5, 47, 15, 36, 26] 이런 배열이 있다.
분할 단계 : 배열을 계속해서 반으로 나누어 각각 작은 배열로 분할한다
[3] [44] [38] [5] [47] [15] [36] [26]
합병 단계: 각 작은 배열을 정렬하고 병합합니다.
작은 배열은 이미 정렬되어 있으므로 이들을 병합하면서 정렬을 수행한다.
[3, 44] [5, 38] [15, 47] [26, 36]
[3, 44]와 [5, 38]을 병합하면 [3, 5, 38, 44].
[15, 47]와 [26, 36]을 병합하면 [15, 26, 36, 47]
다 합치는 단계:작은 배열들을 모두 정렬하여 최종적으로 전체 배열을 병합한다.
[3, 5, 38, 44] [15, 26, 36, 47]
[3, 5, 38, 44]와 [15, 26, 36, 47]을 병합하면 [3, 5, 15, 26, 36, 38, 44, 47]가 된다
코드
// 10 24 76 73 72 1 9
function mergeSort(arr) {
if (arr.length <= 1) return arr;
let mid = Math.floor(arr.length / 2);
// 배열을 두 부분으로 나누어 재귀적으로 합병 정렬
let left = mergeSort(arr.slice(0, mid));
let right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(arr1, arr2) {
let mergedArr = [];
let leftIndex = 0;
let rightIndex = 0;
// 두 배열을 비교하면서 작은 값을 mergedArr에 추가
while (leftIndex < arr1.length && rightIndex < arr2.length) {
if (arr1[leftIndex] <= arr2[rightIndex]) {
mergedArr.push(arr1[leftIndex]);
leftIndex++;
} else {
mergedArr.push(arr2[rightIndex]);
rightIndex++;
}
}
// arr1이나 arr2의 요소가 남아있는 경우, 나머지 요소들을 순서대로 추가
while (leftIndex < arr1.length) {
mergedArr.push(arr1[leftIndex]);
leftIndex++;
}
while (rightIndex < arr2.length) {
mergedArr.push(arr2[rightIndex]);
rightIndex++;
}
return mergedArr;
}
console.log(mergeSort([10, 24, 76, 73, 72, 1, 9]));