병합 정렬: 반갈죽의 미학

재귀를 이해하고 싶어서

나는 알고리즘을 처음 배울 때 재귀(Recursion)가 정말 이해가 안 갔다. 함수가 자기 자신을 호출한다는 게 머릿속에서 뒤죽박죽이 됐다. "이게 언제 끝나? 무한 루프 아니야?" 하는 생각뿐이었다.

그런데 병합 정렬(Merge Sort)을 공부하면서 재귀가 처음으로 와닿았다. 병합 정렬은 재귀의 본질을 정말 명확하게 보여준다. "큰 문제를 작은 문제로 쪼개고, 작은 문제가 해결되면 다시 합친다"는 분할 정복(Divide and Conquer)의 정석이다.

처음엔 "왜 굳이 반으로 쪼개? 그냥 처음부터 비교하면 되잖아?"라고 생각했는데, 이 알고리즘을 손으로 한 번 그려보니까 이해가 됐다. 이 정리는 그때 내가 깨달은 것들을 나를 위해 기록한 노트다.

일단 무조건 반으로 쪼갠다

병합 정렬의 첫 번째 단계는 정말 단순하다. 일단 배열을 반으로 자른다. 그리고 또 반으로 자른다. 원소가 1개가 남을 때까지 계속 자른다.

예를 들어 [38, 27, 43, 3, 9, 82, 10]이라는 배열이 있다면:

[38, 27, 43, 3, 9, 82, 10]
         |
    분할 시작
         ↓
[38, 27, 43, 3] | [9, 82, 10]
         ↓              ↓
[38, 27] | [43, 3]   [9, 82] | [10]
    ↓         ↓         ↓        ↓
[38] | [27] [43] | [3] [9] | [82] [10]

원소가 1개만 남으면 더 이상 쪼갤 수 없다. 1개짜리 배열은 이미 정렬된 상태다. 이게 재귀의 종료 조건이다. 나는 이 부분에서 "아, 재귀는 언젠가 끝나는구나"를 처음 받아들였다.

합치면서 정렬한다 - 여기가 핵심이다

쪼개는 건 쉽다. 그냥 반으로 자르기만 하면 되니까. 병합 정렬의 진짜 핵심은 합치는 과정(Merge)에 있다.

두 개의 정렬된 배열을 합칠 때, 각 배열의 맨 앞 원소를 비교해서 더 작은 걸 먼저 새 배열에 넣는다. 이 과정을 반복하면 전체가 정렬된 배열이 만들어진다.

예를 들어 [27, 38]과 [3, 43]을 합친다고 해보자:

왼쪽: [27, 38]  오른쪽: [3, 43]  결과: []

1단계: 27 vs 3  → 3이 더 작다  → [3]
       왼쪽: [27, 38]  오른쪽: [43]

2단계: 27 vs 43 → 27이 더 작다 → [3, 27]
       왼쪽: [38]  오른쪽: [43]

3단계: 38 vs 43 → 38이 더 작다 → [3, 27, 38]
       왼쪽: []  오른쪽: [43]

4단계: 왼쪽이 비었다 → 오른쪽 전부 넣기 → [3, 27, 38, 43]

나는 이 과정을 "두 줄로 서 있는 사람들을 키 순서로 한 줄로 합치기"로 이해했다. 각 줄의 맨 앞 사람끼리만 비교하면 되니까 O(n)이면 충분하다.

전체 과정을 그림으로 그려봤다

[38, 27, 43, 3, 9, 82, 10]을 완전히 정렬하는 과정은 이렇다:

                [38, 27, 43, 3, 9, 82, 10]
                          |
                  (반으로 쪼개기)
                          ↓
              [38, 27, 43, 3] | [9, 82, 10]
                  |                   |
            (또 쪼개기)           (또 쪼개기)
                  ↓                   ↓
          [38, 27] | [43, 3]     [9, 82] | [10]
            |           |           |        |
         (쪼개기)    (쪼개기)    (쪼개기)   (1개)
            ↓           ↓           ↓        ↓
       [38] | [27]  [43] | [3]  [9] | [82]  [10]
         ↓       ↓     ↓      ↓    ↓      ↓    ↓
       (정렬됨) (정렬됨) (정렬됨) (정렬됨) ... (모두 1개라 정렬됨)

         이제 합치면서 정렬 (Merge 단계)
                      ↑
       [27, 38]    [3, 43]    [9, 82]    [10]
            \         /            \        /
             (합치기)               (합치기)
                 ↓                     ↓
          [3, 27, 38, 43]         [9, 10, 82]
                  \                   /
                   \   (마지막 합치기)  /
                    \                /
                           ↓
              [3, 9, 10, 27, 38, 43, 82]

손으로 한 번 그려보니까 "아, 재귀는 이렇게 돌아가는구나"가 확 와닿았다. 아래로 내려가면서 쪼개고, 위로 올라오면서 합친다. 스택(Stack)처럼 쌓였다가 풀리는 느낌이었다.

코드로 구현해보니 더 명확했다

JavaScript로 병합 정렬을 구현하면 이렇게 된다:

function mergeSort(arr) {
  // 재귀 종료 조건: 원소가 1개 이하면 이미 정렬됨
  if (arr.length <= 1) {
    return arr;
  }

  // 1단계: 반으로 쪼개기 (Divide)
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

  // 2단계: 재귀적으로 각각 정렬 (Conquer)
  const sortedLeft = mergeSort(left);
  const sortedRight = mergeSort(right);

  // 3단계: 정렬된 두 배열을 합치기 (Merge)
  return merge(sortedLeft, sortedRight);
}

function merge(left, right) {
  const result = [];
  let i = 0; // left 인덱스
  let j = 0; // right 인덱스

  // 두 배열의 원소를 하나씩 비교하면서 작은 걸 result에 추가
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }

  // 남은 원소들 전부 추가 (이미 정렬되어 있음)
  while (i < left.length) {
    result.push(left[i]);
    i++;
  }

  while (j < right.length) {
    result.push(right[j]);
    j++;
  }

  return result;
}

// 테스트
const arr = [38, 27, 43, 3, 9, 82, 10];
console.log(mergeSort(arr)); // [3, 9, 10, 27, 38, 43, 82]

나는 이 코드를 직접 디버거로 돌려보면서 각 단계마다 배열이 어떻게 쪼개지고 합쳐지는지 확인했다. 그때 재귀가 정말 이해됐다.

시간 복잡도 - 왜 항상 O(n log n)인가

병합 정렬의 가장 큰 특징은 무슨 일이 있어도 O(n log n)이라는 점이다. 최악의 경우에도, 최선의 경우에도, 평균적으로도 무조건 O(n log n)이다.

이유는 간단하다:

1. 쪼개는 횟수: 배열을 반으로 계속 나누면 log n번 나눠진다. 예를 들어 원소 8개면 3번(2³ = 8), 16개면 4번(2⁴ = 16) 쪼개지면 원소가 1개씩 남는다.
2. 각 레벨에서 합치는 비용: 각 레벨에서 모든 원소를 한 번씩 비교하니까 O(n)이 걸린다.
3. 전체: 레벨이 log n개, 각 레벨마다 O(n) → O(n log n)

이게 병합 정렬이 "모범생"인 이유다. 퀵 정렬은 운이 나쁘면(이미 정렬된 배열 같은 경우) O(n²)까지 느려질 수 있는데, 병합 정렬은 그런 변수가 없다. 항상 일정하다.

공간 복잡도 - 메모리를 2배로 먹는다

하지만 병합 정렬의 단점도 명확하다. 메모리를 O(n)만큼 추가로 쓴다.

merge() 함수를 보면 result라는 새 배열을 만든다. 원본 배열과 같은 크기의 임시 배열이 필요하다는 뜻이다. 퀵 정렬은 제자리에서 정렬하니까(In-place) 추가 메모리가 거의 안 드는데, 병합 정렬은 그렇지 않다.

나는 이걸 "과자를 정리하려면 빈 상자가 하나 더 필요한 것"으로 이해했다. 두 상자에 있는 과자를 크기 순으로 합치려면 임시로 쓸 빈 상자가 필요하다는 느낌.

메모리가 부족한 임베디드 시스템이나 모바일 환경에서는 이게 치명적일 수 있다.

Stability(안정성) - 같은 값의 순서가 보존된다

병합 정렬은 Stable Sort다. 같은 값을 가진 원소들의 원래 순서가 유지된다는 뜻이다.

예를 들어 [3a, 1, 3b, 2]라는 배열이 있을 때(3a와 3b는 값은 같지만 원래 위치가 다름):

• Stable Sort: [1, 2, 3a, 3b] (원래 3a가 3b보다 앞에 있었으니 정렬 후에도 앞에)
• Unstable Sort: [1, 2, 3b, 3a] (순서가 바뀔 수 있음)

이게 왜 중요하냐면, 여러 기준으로 정렬할 때 순서가 꼬이지 않기 때문이다. 예를 들어 학생 데이터를 먼저 이름 순으로 정렬하고, 그 다음 성적 순으로 정렬한다면, 같은 성적의 학생들은 여전히 이름 순으로 정렬되어 있어야 한다.

병합 정렬은 merge() 함수에서 left[i] <= right[j]가 아니라 left[i] < right[j]로 비교하기 때문에(같을 때 왼쪽을 먼저 택함) 안정성이 보장된다.

퀵 정렬과 비교하면 성격이 정반대다

나는 병합 정렬을 퀵 정렬과 비교하면서 완전히 이해했다. 둘 다 분할 정복을 쓰지만 성격이 정반대다:

특징	퀵 정렬 (Quick Sort)	병합 정렬 (Merge Sort)
쪼개는 방식	Pivot 기준으로 작은 것/큰 것 나눔 (논리적)	그냥 무조건 반으로 자름 (물리적)
정렬 시점	쪼갤 때 이미 정렬	합칠 때 정렬
시간 복잡도	평균 O(n log n), 최악 O(n²)	무조건 O(n log n)
공간 복잡도	O(log n) (재귀 스택만)	O(n) (추가 배열)
안정성	Unstable	Stable
성격	도박사 (빠르지만 변수 있음)	모범생 (느리지만 확실함)

결국 나는 이렇게 정리했다:

• 퀵 정렬: "피벗 잘 골라서 확 나누고 빠르게 끝내자" (공격적)
• 병합 정렬: "일단 반으로 다 쪼개고 천천히 합치면서 확실하게 정렬하자" (방어적)

실제로는 어떻게 쓰일까

병합 정렬은 실제로도 많이 쓰인다. 특히 외부 정렬(External Sort)에서 필수적이다.

1. 외부 정렬 (External Sort)

메모리보다 큰 데이터를 정렬해야 할 때가 있다. 예를 들어 100GB짜리 파일을 4GB 램으로 정렬해야 한다면?

1. 파일을 4GB씩 쪼개서 각각 메모리에 올리고 정렬한 뒤 디스크에 저장
2. 정렬된 작은 파일들을 병합 정렬 방식으로 합치기

디스크 I/O가 비싸니까 순차적으로 읽는 병합 정렬이 랜덤 액세스가 많은 퀵 정렬보다 유리하다.

2. Timsort (Python, Java)

Python의 sorted()나 Java의 Arrays.sort()는 Timsort를 쓴다. Timsort는 병합 정렬과 삽입 정렬을 합친 하이브리드 알고리즘이다.

• 작은 구간은 삽입 정렬로 빠르게 처리
• 큰 구간은 병합 정렬로 안정적으로 정렬

병합 정렬의 안정성과 예측 가능한 성능이 실제로 중요하기 때문에 선택된 것이다.

3. 링크드 리스트 정렬

배열이 아니라 링크드 리스트를 정렬할 때도 병합 정렬이 유리하다. 퀵 정렬은 랜덤 액세스가 필요한데, 링크드 리스트는 O(n)이 걸린다. 반면 병합 정렬은 순차적으로만 접근하니까 링크드 리스트에도 효율적이다.

Bottom-Up 병합 정렬 - 재귀 없이도 가능하다

병합 정렬은 재귀로만 구현하는 게 아니다. 반복문(Iteration)으로도 구현할 수 있다. 이걸 Bottom-Up 방식이라고 한다.

function mergeSortBottomUp(arr) {
  const n = arr.length;
  let result = [...arr]; // 복사본

  // size: 합칠 부분 배열의 크기 (1, 2, 4, 8, ...)
  for (let size = 1; size < n; size *= 2) {
    for (let start = 0; start < n; start += size * 2) {
      const mid = Math.min(start + size, n);
      const end = Math.min(start + size * 2, n);

      // [start, mid)와 [mid, end) 합치기
      const left = result.slice(start, mid);
      const right = result.slice(mid, end);
      const merged = merge(left, right);

      // 합친 결과를 다시 result에 복사
      for (let i = 0; i < merged.length; i++) {
        result[start + i] = merged[i];
      }
    }
  }

  return result;
}

이 방식은 재귀 호출 스택을 쓰지 않아서 스택 오버플로우 위험이 없다는 장점이 있다. 대용량 데이터를 처리할 때 유용하다.

마치며

병합 정렬은 나에게 재귀를 이해하게 해준 고마운 알고리즘이다. "큰 문제를 작은 문제로 쪼개고, 작은 문제의 해답을 합쳐서 큰 문제를 푼다"는 분할 정복의 본질을 손으로 그려보면서 깨달았다.

실제로 쓸까 말까를 고민할 때는 이렇게 정리했다:

병합 정렬을 선택하는 경우:

• 안정성이 중요할 때 (같은 값의 순서 보존)
• 최악의 경우에도 O(n log n)을 보장해야 할 때
• 링크드 리스트나 외부 정렬처럼 순차 접근이 유리한 경우
• 메모리가 충분할 때

퀵 정렬을 선택하는 경우:

• 평균적으로 가장 빠른 성능이 필요할 때
• 메모리가 부족할 때 (In-place 정렬)
• 안정성이 중요하지 않을 때

결국 병합 정렬은 "느리지만 확실한 모범생"이고, 퀵 정렬은 "빠르지만 변수가 있는 도박사"다. 나는 이 두 알고리즘을 비교하면서 분할 정복의 다양한 얼굴을 이해하게 됐다.