병합 정렬: 작은 정렬 결과를 두 포인터로 합치기

병합 정렬은 반으로 나눈 두 구간을 각각 정렬한 뒤 작은 맨 앞값부터 꺼내 합칩니다. 나누는 일보다 정렬된 두 결과를 올바르게 합치는 규칙이 핵심입니다.

선수 지식: 재귀의 종료 조건, 배열 구간, 두 정렬 배열 병합

• 길이 0·1인 구간을 기저 조건으로 삼습니다.
• 두 포인터가 가리키는 값만 비교해도 되는 이유를 설명합니다.
• 보조 배열을 재사용하여 병합마다 선형 작업만 수행합니다.

구간을 나누고 작은 결과의 의미를 믿습니다

[4, 1, 3, 2]를 가운데에서 나누면 [4, 1]과 [3, 2]입니다. 두 구간을 각각 정렬하면 [1, 4]와 [2, 3]이 됩니다. 이제 두 구간의 맨 앞값 1과 2를 비교하여 작은 1부터 꺼내면 전체에서 가장 작은 값을 선택할 수 있습니다. 두 구간 내부가 이미 정렬되어 있다는 전제가 이 선택을 가능하게 합니다.

재귀 함수는 [left, right), 즉 left를 포함하고 right를 제외하는 반열린 구간을 처리합니다. 길이는 right – left이며 길이가 0 또는 1이면 이미 정렬되어 있으므로 끝냅니다. 중간점 mid를 기준으로 [left, mid)와 [mid, right)로 나누면 원소가 빠지거나 겹치지 않습니다.

재귀 호출은 두 구간이 정렬되었다는 결과를 만든 뒤 반환합니다. 부모 호출은 다시 구간 안을 정렬할 필요 없이 병합에만 집중합니다. 반으로 나눈다는 사실만으로 정렬되는 것은 아닙니다. 작은 결과의 정확성과 그 결과를 합치는 규칙이 함께 맞아야 전체 배열의 정렬이 완성됩니다.

현재 맨 앞 두 값 중 작은 쪽만 소비합니다

값을 하나 꺼냈을 때 그쪽 포인터만 한 칸 전진합니다. 반대편 후보는 아직 결과에 넣지 않았으므로 그대로 남아 다음 비교에 참여합니다. 한쪽이 끝나면 다른 쪽의 남은 값은 이미 정렬되어 있어 더 비교하지 않고 붙입니다. 각 원소를 한 번씩 쓰므로 두 구간 길이 합이 k일 때 병합은 O(k) 작업입니다.

비교 중인 구간을 덮어쓰지 않도록 공간을 나눕니다

아직 읽어야 할 원본 구간에 병합 결과를 바로 쓰면 값이 덮여 사라질 수 있습니다. 예제는 별도 보조 배열 buffer에 현재 구간의 정렬 결과를 쓴 뒤 같은 구간으로 복사합니다. buffer의 다른 구간에 예전 값이 남아 있어도 읽지 않으므로 지울 필요가 없습니다. 각 병합에서 쓸 범위만 정확히 채우는 것이 중요합니다.

보조 배열은 정렬 시작 때 길이 n으로 한 번만 만듭니다. 병합마다 인덱스 0부터 right까지 새 배열을 초기화하면 현재 작은 구간과 무관한 앞쪽까지 반복해서 쓰게 됩니다. 특히 낮은 단계의 작은 구간이 많을 때 큰 인덱스까지 채우는 작업이 누적되어 O(n²)까지 커질 수 있습니다. 병합이 선형이라는 설명에는 현재 구간 길이에 비례한 준비 작업이라는 조건도 들어 있습니다.

두 후보가 같으면 왼쪽 구간을 먼저 선택하는 <=를 사용합니다. 왼쪽 구간의 항목은 원래 배열에서도 오른쪽 구간의 항목보다 먼저 있었으므로 동률 순서가 유지됩니다. 자식 구간도 같은 규칙으로 정렬되므로 전체 병합 정렬은 안정적입니다. 반대로 항상 오른쪽 동률을 먼저 선택하면 이 성질이 깨집니다.

각 층의 전체 길이와 나누는 깊이를 곱합니다

한 재귀 층에서 서로 겹치지 않는 구간들을 병합하며, 그 길이를 모두 더하면 n입니다. 구간을 반으로 계속 나누는 깊이는 O(log n)이므로 전체 시간은 O(n log n)입니다. 이 구현은 이미 정렬된 두 구간이라도 병합을 생략하지 않으므로 처음부터 정렬된 입력의 시간도 O(n log n)입니다. 입력 검사와 복사는 O(n)으로 이 범위에 포함됩니다.

함수는 빈 칸 없는 유한 숫자 배열을 복사해 정렬된 새 배열을 반환합니다. 빈 배열은 재귀가 바로 끝나며 음수와 중복도 허용합니다. NaN·문자열·무한대·희소 배열은 거절합니다. 반환 배열과 보조 배열은 각각 O(n), 호출 스택은 O(log n)이므로 전체 추가 공간은 O(n)입니다. 재귀라는 이유만으로 공간을 깊이만큼만 세면 보조 배열을 빠뜨립니다.

전체 코드와 직접 실행

개념을 읽었다면 아래 예제를 직접 실행하며 상태 변화를 확인할 수 있습니다.

function copyFiniteNumbers(values) {
  if (!Array.isArray(values)) throw new TypeError('숫자 배열이 필요합니다.');
  for (let i = 0; i < values.length; i++) {
    if (!Object.hasOwn(values, i) || !Number.isFinite(values[i])) {
      throw new TypeError('빈 칸 없는 유한 숫자 배열이 필요합니다.');
    }
  }
  return values.slice();
}

function mergeSort(values) {
  const a = copyFiniteNumbers(values);
  const buffer = new Array(a.length);
  function sort(left, right) {
    if (right - left < 2) return;
    const mid = left + Math.floor((right - left) / 2);
    sort(left, mid);
    sort(mid, right);
    let i = left;
    let j = mid;
    let write = left;
    while (i < mid && j < right) {
      buffer[write++] = a[i] <= a[j] ? a[i++] : a[j++];
    }
    while (i < mid) buffer[write++] = a[i++];
    while (j < right) buffer[write++] = a[j++];
    for (let k = left; k < right; k++) a[k] = buffer[k];
  }
  sort(0, a.length);
  return a;
}

const input = [4, 1, 3, 2];
console.log(JSON.stringify(mergeSort(input)));
console.log(JSON.stringify(input));
console.log(JSON.stringify(mergeSort([3, -1, 3, 0])));

node javascript-merge-sort-shared-buffer.mjs

[1,2,3,4]
[4,1,3,2]
[-1,0,3,3]

비용과 적용 범위

시간: 최선·평균·최악 O(n log n)

공간: O(n)

분석 조건: n은 배열 길이이며 n≤1은 O(1) 정렬 작업입니다. 길이 n의 보조 배열을 한 번 만들고 현재 병합 구간만 씁니다. 반환 복사본과 호출 스택까지 공간에 포함하며, 동률에서 왼쪽을 먼저 골라 안정적입니다.

직접 확인해 보기

정렬된 [1, 5]와 [2, 4]를 합칠 때 처음 세 번 고르는 값과 그때 움직이는 포인터를 적어 보세요.

함께 읽을 글

• 코딩테스트 투 포인터 풀이: 두 정렬 배열 합치기 — 두 정렬 배열을 합치는 병합 한 단계를 먼저 연습합니다.
• 투 포인터의 이동 기준: 양끝 비교와 정렬 배열 병합 — 값을 소비한 포인터만 옮기는 기준을 복습합니다.
• JavaScript 배열: 인덱스 조회와 삽입·삭제 비용 — 배열 복사와 임시 저장 비용을 분석합니다.

참고 자료

• Competitive Programmer’s Handbook — Sorting — 정렬 장의 버블 정렬, 병합 정렬 및 비교 정렬의 시간 분석을 참고했습니다. 예제와 추적 설명은 직접 작성했습니다.
• Princeton Algorithms — Mergesort — 반분·정렬·병합 구조, 보조 배열과 안정성, 선형 병합을 전제로 한 n log n 분석을 참고했습니다.