정렬 과정에서 분할 정복 알고리즘을 사용하기 때문에 하위 문제들을 어떻게 구성해야 하는지 결정해야 합니다. 궁극적인 목표는 전체 배열을 정렬하는 것입니다. 하위 문제는 하위 배열을 정렬하는 것이라고 합시다. 특히 하위 문제를 인덱스 p에서 시작하여 인덱스 r까지 정렬해야 하는 문제로 간주합니다. 하위 배열은 다르게 표기하는 것이 편리할 듯하니 array[p..r]array의 하위 배열을 나타낸다고 합시다. 이처럼 점 두 개를 쓰는 것은 JavaScript의 문법에는 맞지 않지만 여기서는 알고리즘을 코드로 구체적으로 구현하는 것이 아니므로 알고리즘을 기술하기 위해 이렇게 쓰겠습니다. 이 표기법에 따르면 n개 요소를 가진 배열에 대해 원래 문제는 array[0..n-1]을 정렬하는 것이라고 할 수 있습니다.
아래는 분할 정복 알고리즘을 이용하여 어떻게 병합 정렬을 하는지 보여줍니다:
  1. Divide by finding the number q of the position midway between p and r. Do this step the same way we found the midpoint in binary search: add p and r, divide by 2, and round down.
  2. Conquer by recursively sorting the subarrays in each of the two subproblems created by the divide step. That is, recursively sort the subarray array[p..q] and recursively sort the subarray array[q+1..r].
  3. Combine by merging the two sorted subarrays back into the single sorted subarray array[p..r].
또한, 탈출 조건이 필요합니다. 탈출 조건은 2개 미만의 요소가 포함된 하위 배열로, 이는 p, is greater than or equal to, r인 경우입니다. 요소가 하나도 없거나 하나만 있는 하위 배열은 이미 정렬되어 있는 것과 같습니다. 그러므로 p, is less than, r일 때만 분할-정복-결합 과정을 거칩니다.
예제를 하나 살펴봅시다. [14, 7, 3, 12, 9, 11, 6, 2]가 있는 array로 시작합니다. 첫 번째 하위 배열은 완전한 전체 배열 array[0..7](p, equals, 0, r, equals, 7)입니다. 이 하위 배열은 2개 이상의 요소를 가지므로 탈출 조건에 맞지 않습니다.
  • 분할 단계에서 q, equals, 3 입니다.
  • 정복 단계에서는 [14, 7, 3, 12] 값이 포함된 array[0..3]과 [9, 11, 6, 2]가 포함된 array[4..7]을 정렬합니다. 정복 단계를 끝내면 각각의 두 하위 배열은 정렬이 되어 있습니다: array[0..3]에는 [3, 7, 12, 14]와 같이 값이 들어 있고 array[4..7]는 [2, 6, 9, 11]와 같이 되어 있습니다. 그러므로 완전한 배열은 [3, 7, 12, 14, 2, 6, 9, 11]이 됩니다.
  • 마지막으로 결합 단계에서는 반으로 나눈 앞 쪽과 뒷 쪽으로 된 두 정렬된 하위 배열을 병합해서 마지막으로 정렬된 배열 [2, 3, 6, 7, 9, 11, 12, 14] 를 얻게 됩니다.
하위 배열 array[0..3]은 어떻게 정렬되었을까요? 마찬가지입니다. 2개 이상의 요소로 되어 있기 때문에 이것은 탈출 조건이 아닙니다. p, equals, 0이고 r, equals, 3이므로 q, equals, 1이고 array[0..1] ([14, 7])과 array[2..3] ([3, 12]) 를 재귀적으로 정렬하여 [7, 14, 3, 12] 값을 갖는 array[0..3]을 얻게 됩니다. 앞쪽 반과 뒷쪽 반을 병합하면 [3, 7, 12, 14]가 됩니다.
하위 배열 array[0..1]은 어떻게 정렬되었을까요? p, equals, 0이고 r, equals, 1이므로 q, equals, 0이고 array[0..0] ([14])와 array[1..1] ([7])을 재귀적으로 정렬하여 여전히 [14, 7]을 포함하고 있는 array[0..1]을 얻습니다. 그런 후 앞 쪽과 뒤 쪽을 병합하여 [7, 14]를 얻습니다.
하위 배열 array[0..0]array[1..1]은 각각 2개 미만의 요소를 갖고 있으므로 탈출 조건입니다. 다음은 병합 정렬 알고리즘 전체가 전개되는 과정을 나타냅니다:
병합 정렬
병합 정렬에서 대부분의 단계는 간단합니다. 탈출 조건은 쉽게 점검할 수 있습니다. 분할 단계에서 중간점인 q를 찾는 것 역시 매우 쉽습니다. 정복 단계에서는 재귀 호출을 두 번 해야 합니다. 병합 단계에서 두 하위 배열을 합칠때 진짜 정렬이 일어납니다. 잠시 두 정렬된 하위 배열을 어떻게 효율적으로 병합하는지 알고 있다고 가정하고 계속해서 병합 정렬를 전체적으로 살펴보도록 합시다.

위 자료는 다트머스 대학교 컴퓨터공학과토마스 콜먼 교수와 데빈 발컴 교수, 그리고 칸아카데미 컴퓨팅 과정 팀이 공동으로 저술했으며, 본 내용물의 저작권은 CC-BY-NC-SA 라이선스를 적용합니다.