정렬 과정에서 분할 정복 알고리즘을 사용하기 때문에 하위 문제들을 어떻게 구성해야 하는지 결정해야 합니다. 궁극적인 목표는 전체 배열을 정렬하는 것입니다. 하위 문제는 하위 배열을 정렬하는 것이라고 합시다. 특히 하위 문제를 인덱스 p p 에서 시작하여 인덱스 r r 까지 정렬해야 하는 문제로 간주합니다. 하위 배열은 다르게 표기하는 것이 편리할 듯하니 array[p..r]array의 하위 배열을 나타낸다고 합시다. 이처럼 점 두 개를 쓰는 것은 JavaScript의 문법에는 맞지 않지만 여기서는 알고리즘을 코드로 구체적으로 구현하는 것이 아니므로 알고리즘을 기술하기 위해 이렇게 쓰겠습니다. 이 표기법에 따르면 n n 개 요소를 가진 배열에 대해 원래 문제는 array[0..n-1]을 정렬하는 것이라고 할 수 있습니다.
아래는 분할 정복 알고리즘을 이용하여 어떻게 병합 정렬을 하는지 보여줍니다:
  1. 분할. p p r r 의 중간 q q 를 찾습니다. 이진 검색에서 중간점을 찾았던 것과 같은 방법으로 이 과정을 수행합니다: p p r r 을 더해서 2로 나눈 후 내림을 하여 정수로 만듭니다.
  2. 정복. 분할 단계에서 만들어진 두 하위 문제 각각에 있는 하위 배열을 재귀적으로 정렬합니다. 즉 하위 배열 array[p..q]를 재귀적으로 정렬하고 또 하위 배열array[q+1..r]을 재귀적으로 정렬합니다.
  3. 결합. 정렬된 두 하위 배열을 하나의 정렬된 하위 배열인 array[p..r]로 결합합니다.
또한, 탈출 조건이 필요합니다. 탈출 조건은 2개 미만의 요소가 포함된 하위 배열로, 이는 pr p \geq r 인 경우입니다. 요소가 하나도 없거나 하나만 있는 하위 배열은 이미 정렬되어 있는 것과 같습니다. 그러므로 p<r p < r 일 때만 분할-정복-결합 과정을 거칩니다.
예제를 하나 살펴봅시다. [14, 7, 3, 12, 9, 11, 6, 2]가 있는 array로 시작합니다. 첫 번째 하위 배열은 완전한 전체 배열 array[0..7](p=0 p=0 , r=7 r=7 )입니다. 이 하위 배열은 2개 이상의 요소를 가지므로 탈출 조건에 맞지 않습니다.
  • 분할 단계에서 q=3 q = 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=0 p=0 이고 r=3 r=3 이므로 q=1 q=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=0 p=0 이고 r=1 r=1 이므로 q=0 q=0 이고 array[0..0] ([14])와 array[1..1] ([7])을 재귀적으로 정렬하여 여전히 [14, 7]을 포함하고 있는 array[0..1]을 얻습니다. 그런 후 앞 쪽과 뒤 쪽을 병합하여 [7, 14]를 얻습니다.
하위 배열 array[0..0]array[1..1]은 각각 2개 미만의 요소를 갖고 있으므로 탈출 조건입니다. 다음은 병합 정렬 알고리즘 전체가 전개되는 과정을 나타냅니다:
병합 정렬 대부분의 과정은 간단합니다. 탈출 조건을 확인하는 것도 간단합니다. 분할 단계에서 q q 를 찾는 것도 아주 쉽습니다. 정복 단계에서는 재귀 호출을 두 번만 하면 됩니다. 실제로 정렬이 진행되는 곳은 바로 결합 단계입니다.
다음 심화문제에서는 병합 정렬을 구현해보고, 재귀적으로 분할 정복하는 방법을 이해할 수 있도록 해 보겠습니다. 그러고 나서 그다음 심화 문제에서는 두 정렬된 하위 배열을 어떻게 효율적으로 결합하는지 알아보도록 하겠습니다.

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