병합 정렬 (Merge Sort)

분할 정복(Divide and Conquer) 알고리즘의 일종으로, 배열을 더 작은 하위 배열로 나누고, 각 하위 배열을 비교하여 정렬한 다음에 정렬된 하위 배열을 병합하여 최종적으로 정렬된 배열을 만드는 정렬 알고리즘입니다.

병합 정렬의 특징

동 작

병합 정렬은 더 이상 나눌 수 없을 때까지 배열을 계속해서 반으로 분할하는 재귀 알고리즘입니다. 즉, 배열에 요소가 하나만 남을 때까지 분할하고(요소가 하나인 배열은 하나 자체로 정렬된 상태이므로), 정렬하면서 차례로 합칩니다. 정렬된 부분 배열들을 반복적으로 병합하여 전체를 정렬합니다.

시간 복잡도

단계	설명	비용
분할 단계	배열을 log₂N 단계로 나눔	O(log N)
병합 단계	각 단계에서 모든 원소 병합	O(N)
총합	O(N log N)	매우 효율적

최악, 평균, 최선 모두 O(N log N) 으로 안정적인 정렬입니다.

하지만, 병합 시 임시 배열이 필요해 메모리를 추가로 사용하여 메모리 비용이 크다면 퀵 정렬보다 느릴 수 있습니다.

병합 정렬 구현

재귀적 구현

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) {
    const result = [];
    let i = 0, j = 0;

    // 두 배열을 비교하며 정렬된 순서로 병합
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result.push(left[i++]);
        } else {
            result.push(right[j++]);
        }
    }

    // 남은 요소들 추가
    return result.concat(left.slice(i)).concat(right.slice(j));
}