병합정렬(merge sort)은 대표적인 정렬 알고리즘 중 하나로 다음과 같이 동작합니다.
- 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
- 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
- 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
- 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.
출처 : 위키피디아
배열을 하위 배열로 나누고 하나의 요소가 담겨있는 배열은 정렬된 것으로 본다.
위 과정을 재귀로 반복한다.
const arr = [3, 5, 2, 6, 4, 1, 8, 7, 9];
function mergeSort(arr) {
console.log("분할 할 배열", arr);
// 배열의 길이가 0 또는 1이면 그대로 반환
if (arr.length < 2) {
console.log("반환한 배열", arr);
return arr;
}
// 배열의 길이를 반으로 나눈 값을 내림하여 중간값으로 정한다.
const mid = Math.floor(arr.length / 2);
// 배열에서 시작값(0)부터 중간값까지 잘라서 좌측 배열로 정한다.
const leftArr = arr.slice(0, mid);
// 배열에서 중간값부터 마지막값까지 잘라서 우측 배열로 정한다.
const rightArr = arr.slice(mid);
console.log("좌측배열", leftArr, "우측배열", rightArr);
return merge(mergeSort(leftArr), mergeSort(rightArr));
}
// 중간값을 기준으로 나뉘었던 좌측배열과 우측배열을 정렬하여 병합하는 함수
function merge(leftArr, rightArr) {
console.log("병합정렬 할 배열", leftArr, rightArr);
// 정렬된 배열이 들어갈 배열을 선언한다.
const sortedArr = [];
// 좌측배열과 우측배열이 모두 존재하는 동안,
while (leftArr.length && rightArr.length) {
// 좌측배열 첫번째 요소가 우측배열의 첫번째 요소보다 작거나 같으면,
if (leftArr[0] <= rightArr[0]) {
// 좌측배열의 첫번째 요소를 정렬된 배열에 넣고,
sortedArr.push(leftArr.shift());
} else {
// 그 반대라면 우측배열의 첫번째 요소를 정렬된 배열에 넣는다.
sortedArr.push(rightArr.shift());
}
}
console.log("병합정렬 된 배열", [...sortedArr, ...leftArr, ...rightArr]);
// 정렬된 배열과 좌측배열, 우측배열의 남은 값을 하나의 배열로 만들어 반환한다.
return [...sortedArr, ...leftArr, ...rightArr];
}
console.log(mergeSort(arr));
분할 할 배열 [ 3, 5, 2, 6, 4, 1, 8, 7, 9 ]
좌측배열 [ 3, 5, 2, 6 ] 우측배열 [ 4, 1, 8, 7, 9 ]
분할 할 배열 [ 3, 5, 2, 6 ]
좌측배열 [ 3, 5 ] 우측배열 [ 2, 6 ]
분할 할 배열 [ 3, 5 ]
좌측배열 [ 3 ] 우측배열 [ 5 ]
분할 할 배열 [ 3 ]
반환한 배열 [ 3 ]
분할 할 배열 [ 5 ]
반환한 배열 [ 5 ]
병합정렬 할 배열 [ 3 ] [ 5 ]
병합정렬 된 배열 [ 3, 5 ]
분할 할 배열 [ 2, 6 ]
좌측배열 [ 2 ] 우측배열 [ 6 ]
분할 할 배열 [ 2 ]
반환한 배열 [ 2 ]
분할 할 배열 [ 6 ]
반환한 배열 [ 6 ]
병합정렬 할 배열 [ 2 ] [ 6 ]
병합정렬 된 배열 [ 2, 6 ]
병합정렬 할 배열 [ 3, 5 ] [ 2, 6 ]
병합정렬 된 배열 [ 2, 3, 5, 6 ]
분할 할 배열 [ 4, 1, 8, 7, 9 ]
좌측배열 [ 4, 1 ] 우측배열 [ 8, 7, 9 ]
분할 할 배열 [ 4, 1 ]
좌측배열 [ 4 ] 우측배열 [ 1 ]
분할 할 배열 [ 4 ]
반환한 배열 [ 4 ]
분할 할 배열 [ 1 ]
반환한 배열 [ 1 ]
병합정렬 할 배열 [ 4 ] [ 1 ]
병합정렬 된 배열 [ 1, 4 ]
분할 할 배열 [ 8, 7, 9 ]
좌측배열 [ 8 ] 우측배열 [ 7, 9 ]
분할 할 배열 [ 8 ]
반환한 배열 [ 8 ]
분할 할 배열 [ 7, 9 ]
좌측배열 [ 7 ] 우측배열 [ 9 ]
분할 할 배열 [ 7 ]
반환한 배열 [ 7 ]
분할 할 배열 [ 9 ]
반환한 배열 [ 9 ]
병합정렬 할 배열 [ 7 ] [ 9 ]
병합정렬 된 배열 [ 7, 9 ]
병합정렬 할 배열 [ 8 ] [ 7, 9 ]
병합정렬 된 배열 [ 7, 8, 9 ]
병합정렬 할 배열 [ 1, 4 ] [ 7, 8, 9 ]
병합정렬 된 배열 [ 1, 4, 7, 8, 9 ]
병합정렬 할 배열 [ 2, 3, 5, 6 ] [ 1, 4, 7, 8, 9 ]
병합정렬 된 배열 [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]