JavaScript 병합 정렬(Merge Sort)로 배열을 재귀적으로 정렬하는 방법

숫자 배열을 입력받아 병합 정렬(Merge Sort) 알고리즘으로 정렬하는 JavaScript 함수를 작성해 보겠습니다.

병합 정렬이란?

병합 정렬은 대표적인 분할 정복(Divide and Conquer) 알고리즘으로, 크게 두 가지 과정으로 구성됩니다.

• 분할(재귀) 단계 — 배열을 요소가 하나만 남을 때까지 계속 반으로 나눕니다.
• 병합(반복) 단계 — 나뉜 조각들을 올바른 순서대로 다시 합쳐 정렬된 배열을 만듭니다.

이 알고리즘의 시간 복잡도는 최악의 경우에도 O(n log n)으로 안정적이며, 데이터가 어떻게 배치되어 있든 일관된 성능을 보장한다는 장점이 있습니다.

구현 예제

const arr = [23, 4, 67, 32, 1, 7, 56, 5, 89];

const mergeSort = arr => {
    // 요소가 1개 이하면 이미 정렬된 상태
    if (arr.length < 2){
        return arr;
    }
    const middle = Math.floor(arr.length / 2);
    const left = arr.slice(0, middle), right = arr.slice(middle, arr.length);
    // 좌우 배열을 각각 재귀적으로 정렬한 뒤 병합
    return merge(mergeSort(left), mergeSort(right));
};

const merge = (left, right) => {
    const res = [];
    // 두 배열의 앞 요소를 비교해 작은 값부터 결과에 추가
    while (left.length && right.length) {
        if (left[0] <= right[0]){
            res.push(left.shift());
        }
        else{
            res.push(right.shift());
        };
    }
    // 남은 요소들을 모두 추가
    while (left.length){
        res.push(left.shift());
    };
    while (right.length){
        res.push(right.shift());
    };
    return res;
};

console.log(mergeSort(arr));

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다.

[
    1, 4, 5, 7, 23,
    32, 56, 67, 89
]

동작 원리 정리

1. mergeSort 함수는 배열의 길이가 2 미만일 때 그대로 반환하며 재귀를 종료합니다.
2. 배열을 중간 지점 기준으로 left와 right 두 부분으로 나눈 뒤, 각각 재귀 호출로 정렬합니다.
3. merge 함수는 두 정렬된 배열의 첫 번째 요소를 비교하여 더 작은 값을 결과 배열에 순서대로 넣습니다.
4. 한쪽 배열이 소진되면 나머지 배열의 남은 요소들을 그대로 이어 붙여 최종 정렬된 배열을 완성합니다.