If you're seeing this message, it means we're having trouble loading external resources on our website.

웹 필터가 올바르게 작동하지 않으면 도메인 *. kastatic.org*.kasandbox.org이 차단되어 있는지 확인하세요.

주요 내용

병합 정렬이란?

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

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