병합 정렬

언제 쓰나

배열을 정렬하는 대표적인 방법 가운데 하나로, 입력이 어떻게 생겼든 정렬이 O(n log n) 안에 끝나야 할 때 씁니다.

• 정렬을 직접 구현하라고 합니다. 대표 문제인 LeetCode 912는 내장 정렬 함수 없이 O(n log n) 시간에 정렬하라는 조건을 붙입니다.
• 이미 정렬된 두 배열을 하나로 합쳐야 합니다. 정렬된 두 배열이나 연결 리스트를 합치는 문제는 병합 정렬의 합치기 단계를 그대로 씁니다.
• 입력이 어떤 순서로 들어올지 모릅니다. 병합 정렬은 값과 상관없이 늘 반씩 나누기 때문에, 이미 정렬된 입력이든 거꾸로 정렬된 입력이든 걸리는 시간이 같은 O(n log n)입니다.

어떻게 동작하나

정렬된 두 배열을 합쳐 보면

[5, 1, 1, 2, 0, 0]을 반으로 나눈 [5, 1, 1]과 [2, 0, 0]이 각각 이미 [1, 1, 5], [0, 0, 2]로 정렬돼 있다고 해 보겠습니다. 이 두 배열을 하나의 정렬된 배열로 합치는 일은 종이 위에서 이렇게 할 수 있습니다.

1. 두 배열의 맨 앞인 1과 0을 비교해, 더 작은 0을 새 배열에 적습니다. 오른쪽 배열은 다음 칸으로 넘어갑니다.
2. 다시 맨 앞끼리, 1과 0을 비교해 0을 적습니다.
3. 1과 2를 비교해 1을 적습니다. 이번에는 왼쪽 배열이 다음 칸으로 넘어갑니다.
4. 같은 방법으로 1과 2를 적고 나면 오른쪽 배열이 비고, 왼쪽 배열에는 5가 남습니다. 남은 칸은 이미 정렬돼 있으므로 그대로 뒤에 붙입니다. [0, 0, 1, 1, 2, 5] 완성입니다.

두 배열이 각각 정렬돼 있으면 배열의 맨 앞이 그 배열에서 가장 작은 값입니다. 그래서 맨 앞 두 칸만 비교해도 아직 옮기지 않은 값 가운데 가장 작은 값을 찾을 수 있고, 비교 한 번에 새 배열이 한 칸씩 채워집니다. 이렇게 정렬된 두 배열을 하나로 합치는 일을 병합(merge)이라고 합니다.

아래 그림은 위 3번 장면입니다. 파란 칸이 지금 비교하는 두 맨 앞 칸이고, 노란 칸이 방금 채운 자리입니다. 앞서 옮긴 0 두 개는 흐리게 남아 있습니다.

두 배열 합치기 · [1, 1, 5]와 [0, 0, 2]

한 칸이 될 때까지 반씩 나눈다

병합은 두 절반이 이미 정렬돼 있어야 쓸 수 있습니다. 절반을 정렬하는 방법도 같습니다. [5, 1, 1]을 다시 [5]와 [1, 1]로 나누고, [1, 1]도 [1]과 [1]로 나눕니다. 한 칸짜리 배열은 비교할 상대가 없으니 그 자체로 정렬된 상태이고, 여기서부터 거꾸로 병합하며 올라오면 [5, 1, 1]이 [1, 1, 5]가 됩니다.

이처럼 한 칸이 될 때까지 반씩 나눈 뒤 정렬된 절반을 병합하며 올라오는 정렬을 병합 정렬(merge sort)이라고 합니다. 큰 문제를 같은 모양의 작은 문제로 나눠 풀고 그 답을 합치는 방식을 분할 정복(divide and conquer)이라고 부르는데, 병합 정렬이 그 대표적인 예입니다.

아래 시각화는 나누고 합치는 과정을 나무 모양으로 그린 것이고, 읽는 법은 이렇습니다.

• 맨 위 배열이 처음 받은 배열 전체입니다.
• 한 층 내려갈 때마다 배열이 반으로 나뉩니다. 길이가 홀수면 왼쪽 절반이 한 칸 짧습니다.
• 두 절반의 정렬이 끝나면 부모 배열이 비워지고, 두 절반의 맨 앞끼리 비교하며 왼쪽 칸부터 다시 채워집니다.

변수 칸의 값은 아래 풀이 코드의 변수입니다.

• mid: 나눌 때 왼쪽 절반의 길이입니다. [5, 1, 1]이면 Math.floor(3 / 2)인 1이라 [5]와 [1, 1]로 나뉩니다.
• i, j: 합칠 때 왼쪽 배열과 오른쪽 배열에서 지금 보고 있는 칸의 번호입니다. 한 칸을 옮길 때마다 옮긴 쪽의 번호만 1 늘어납니다.
• return: 호출 하나가 끝나며 돌려준 정렬된 배열입니다.

직접 따라가 보기

“다음”을 누르면 한 걸음씩 진행합니다. 2~4번째 단계에서 왼쪽 절반이 한 칸짜리 배열까지 나뉘고, 5번째 단계에서 처음으로 병합이 일어납니다. 13번째 단계부터는 맨 위 배열이 왼쪽 칸부터 한 칸씩 채워지는데, 이때 변수 칸의 i와 j 중 방금 값을 옮긴 쪽만 늘어나는 것을 보세요. 17번째 단계에서 오른쪽 배열이 비어, 왼쪽에 남은 5가 그대로 붙습니다.

처음부터 이전 자동 재생 다음

단계 1 / 18

분할 트리 · nums = [5, 1, 1, 2, 0, 0]

변수

mid

–왼쪽 절반의 길이

i

–왼쪽 배열에서 볼 칸

j

–오른쪽 배열에서 볼 칸

return

–

[5, 1, 1, 2, 0, 0]을 정렬합니다. 한 칸이 될 때까지 반씩 나눈 뒤, 거꾸로 합치며 올라옵니다. "다음"을 눌러 보세요

• 지금 나누거나 채우는 배열
• 비교하는 맨 앞 칸
• 정렬을 마친 배열
• 최종 결과
• 아직 나누지 않은 배열

한 층에서 병합하는 칸을 모두 더하면 원래 배열의 길이 n과 같고, 반씩 나누므로 병합이 일어나는 층은 약 log₂ n개입니다. [5, 1, 1, 2, 0, 0]은 6칸이고 병합이 일어나는 층이 3개입니다. 층마다 n칸을 한 번씩 옮기므로 전체 시간은 O(n log n)입니다.

대표 문제 풀이

LeetCode 912는 정수 배열 nums를 오름차순으로 정렬해 돌려주는 문제로, 내장 정렬 함수를 쓰지 않고 O(n log n) 시간에 풀라는 조건이 붙어 있습니다. 예를 들어 nums = [5, 1, 1, 2, 0, 0]이면 [0, 0, 1, 1, 2, 5]를 돌려줍니다. 풀이 코드는 다음과 같습니다.

var sortArray = function (nums) {
  // ① 한 칸 이하면 이미 정렬돼 있다
  if (nums.length <= 1) {
    return nums;
  }

  // ② 반으로 나눠 각각 정렬한다
  const mid = Math.floor(nums.length / 2);
  const left = sortArray(nums.slice(0, mid));
  const right = sortArray(nums.slice(mid));

  // ③ 정렬된 두 절반을 합친다
  return merge(left, right);
};

function merge(left, right) {
  const result = [];
  let i = 0; // 왼쪽 배열에서 볼 칸
  let j = 0; // 오른쪽 배열에서 볼 칸

  // 맨 앞끼리 비교해 작은 쪽을 옮긴다. 같으면 왼쪽을 먼저 옮긴다
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  // 한쪽이 비면 남은 칸을 그대로 붙인다
  while (i < left.length) result.push(left[i++]);
  while (j < right.length) result.push(right[j++]);
  return result;
}

①이 재귀를 멈추는 조건이고, ②에서 나눈 두 절반을 각각 정렬한 뒤 ③의 merge가 둘을 합칩니다. merge의 첫 while이 맨 앞끼리 비교하는 부분이고, 뒤의 두 while은 한쪽 배열이 먼저 빈 뒤 남은 칸을 붙이는 부분입니다. 첫 while이 끝났을 때는 둘 중 한 배열에만 칸이 남아 있으므로, 뒤의 두 while 가운데 실제로 도는 것은 하나뿐입니다.

left[i] <= right[j]처럼 같은 값이면 왼쪽을 먼저 옮기는 것은 같은 값끼리 원래 순서를 지키기 위해서입니다. 숫자 배열에서는 결과가 달라지지 않지만, 객체 배열을 한 속성으로 정렬할 때는 이 순서가 결과에 드러납니다. 같은 값의 원래 순서를 지키는 정렬을 안정 정렬(stable sort)이라고 합니다.

시간은 위에서 본 것처럼 O(n log n)입니다. 합칠 때마다 새 배열 result를 만들기 때문에 입력 크기만큼의 추가 공간이 필요하고, 그래서 공간은 O(n)입니다.

자주 하는 실수

남은 칸을 붙이지 않습니다. 첫 while만 쓰고 뒤의 두 while을 빠뜨리면, 한쪽 배열이 빈 순간 반복이 끝나 다른 배열에 남은 칸이 버려집니다. [1, 1, 5]와 [0, 0, 2]를 합치는 장면만 보면, 2를 옮긴 뒤 반복이 멈춰 5가 빠진 [0, 0, 1, 1, 2]가 돌아옵니다. 시각화의 17번째 단계가 바로 이 남은 칸을 붙이는 장면입니다.

멈추는 조건을 nums.length === 0으로 씁니다. 길이 1인 배열에서는 mid가 0이라 nums.slice(0, 0)은 빈 배열, nums.slice(0)은 원래와 같은 길이 1짜리 배열이 됩니다. 같은 길이로 다시 호출하니 재귀가 끝나지 않고 호출 스택이 넘칩니다. 한 칸짜리 배열은 이미 정렬된 상태이므로 nums.length <= 1에서 멈춰야 합니다.