정렬 2: 병합 정렬과 퀵 정렬

값 100만 개를 모든 쌍을 비교해서 정렬하면 비교가 약 5,000억 번 필요하지만, 병합 정렬은 약 2,000만 번이면 됩니다.

문제를 쪼개고 반쪽을 풀기

앞 단원의 방법들은 목록 전체를 한꺼번에 다루고, 그 대가로 약 n²번 비교합니다. 이 단원의 두 방법은 분할 정복이라는 다른 계획을 씁니다. 목록을 작은 부분으로 나누고, 각 부분을 같은 방법으로 정렬한 다음, 정렬된 부분을 합칩니다. 나누기는 부분에 값이 하나이거나 없을 때까지 이어지고, 값이 하나뿐인 목록은 이미 정렬된 것입니다. 이 방법은 더 작은 목록에 자기 자신을 다시 쓰므로 재귀적입니다(재귀는 6단원에서 자세히 다룹니다).

병합 정렬: 일은 합치는 데서 합니다

병합 정렬은 목록을 반으로 자르고, 왼쪽 절반을 정렬하고, 오른쪽 절반을 정렬한 뒤, 정렬된 두 절반을 하나로 합칩니다. 재치 있는 부분은 합치기입니다. 정렬된 두 목록은 맨 앞 값만 보고도 합칠 수 있습니다. 두 맨 앞 값을 비교해 작은 값을 적고, 그 값을 지나갑니다. 한쪽이 빌 때까지 되풀이하고, 남은 쪽은 그대로 이어 붙입니다. [1, 4, 7]과 [2, 3, 8]을 합치면 1(1과 2), 2(4와 2), 3(4와 3), 4(4와 8), 7(7과 8) 순서로 적고 마지막 8을 붙입니다. 값 6개에 비교 5번입니다. 값이 모두 n개인 두 목록을 합칠 때 비교는 n − 1번을 넘지 않습니다.

function merge(left, right) {
  const out = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (right[j] < left[i]) out.push(right[j++]);
    else out.push(left[i++]);
  }
  return out.concat(left.slice(i), right.slice(j));
}

function mergeSort(a) {
  if (a.length <= 1) return a;          // already sorted
  const mid = Math.floor(a.length / 2);
  return merge(mergeSort(a.slice(0, mid)), mergeSort(a.slice(mid)));
}

왜 빠를까요? 반으로 나누는 과정을 층으로 그려 봅니다. 값 8개는 4개짜리 2개로, 다시 2개짜리 4개로, 다시 1개짜리 8개로 나뉩니다. 8은 세 번 반으로 가를 수 있으니 층은 셋입니다. 한 층에서 이루어지는 합치기를 모두 더하면 값 하나하나를 한 번씩 다루므로, 한 층에 드는 비교는 많아야 약 n번입니다. 층이 log₂ n개이므로 모두 약 n log₂ n번입니다. 값 100만 개라면 약 2,000만 번으로, 쌍마다 비교하는 방법의 약 5,000억 번과 비교됩니다. [38, 27, 43, 3, 9, 82, 10]을 실험실처럼 [38, 27, 43, 3]과 [9, 82, 10]으로 나누면 비교 14번이면 되고, 위 코드처럼 3개와 4개로 나누면 13번입니다.

대가는 메모리입니다. 합치려면 결과를 적을 곳이 있어야 하므로 병합 정렬은 입력만 한 목록을 하나 더 씁니다. 병합 정렬은 안정적이기도 합니다. 맨 앞 값이 같을 때 왼쪽 목록에서 먼저 가져오므로, 같다고 비교되는 값들이 원래 순서를 지킵니다. 표를 도시로 정렬한 다음 이름으로 정렬하는 것처럼 열을 바꿔 가며 정렬할 때 이 성질이 중요합니다.

퀵 정렬: 피벗을 기준으로 나누기

퀵 정렬은 다른 방식으로 나눕니다. 값 하나를 골라 피벗으로 삼고, 피벗보다 작은 값은 모두 앞으로, 나머지는 뒤로 오도록 목록을 다시 늘어놓습니다. 이 단계를 분할이라고 합니다. 이제 피벗은 최종 자리에 있고, 양쪽은 같은 방법으로 따로 정렬하면 됩니다. 왼쪽 값은 모두 오른쪽 값보다 작으므로 나중에 합칠 일이 없습니다.

실험실은 각 부분의 마지막 값을 피벗으로 쓰는 흔한 교과서 방식을 씁니다. [5, 1, 4, 2, 8]에서 피벗 8을 나머지 네 값과 비교하면 모두 작으므로 8은 끝에 그대로 있습니다. 다음 부분 [5, 1, 4, 2]는 피벗 2를 씁니다. 1만 더 작으므로 교환 두 번 뒤 목록은 [1, 2, 4, 5, 8]이 됩니다. 비교 한 번으로 [4, 5]를 처리하면 끝입니다. 모두 비교 8번, 교환 2번입니다.

피벗이 가운데 근처에 떨어지면 나눌 때마다 문제가 반으로 줄어 퀵 정렬도 병합 정렬처럼 약 n log₂ n번 비교합니다. 게다가 복사본 없이 원래 목록 안에서 일합니다. 하지만 피벗을 잘못 고르면 손해를 봅니다. 이미 정렬된 목록에서 늘 마지막 값을 피벗으로 쓰면 나눌 때마다 값이 하나씩만 떨어져 나가고, 퀵 정렬은 약 n²/2번 비교로 돌아갑니다. [1, 2, 3, 4, 5]라면 선택 정렬과 같은 10번입니다. 실제 라이브러리는 피벗을 무작위로 고르거나 표본 세 값의 가운데 값을 쓰는 식으로 더 조심해서 고릅니다.