선형 시간 병합하기

병합 정렬에서 남은 부분은 이웃한 두 정렬된 하위 배열, array[p..q]와 array[q+1..r]을 하나의 정렬된 하위 배열 array[p..r]로 병합하는 merge 함수입니다. 이 함수를 어떻게 최대한 효율적으로 구축할지 알아보도록 합시다. 두 하위 배열에 총 $n$‍개의 요소가 있다고 합시다. 이들을 하나로 병합하기 위해 각 요소를 검사해야 하므로 최상의 경우 병합 시간이 $\mathrm{\Theta }(n)$‍이 됩니다. 이제 총 $n$‍ 요소를 $\mathrm{\Theta }(n)$‍ 시간 내에 어떻게 병합할지 알아볼 것입니다.

정렬된 하위 배열 array[p..q]와 array[q+1..r]을 병합하고 결과적으로 array[p..r]을 얻기 위해서는 임시 배열을 만들어 array[p..q]와 배열[q+1..r]을 이 임시 배열로 복사하는 작업을 먼저 해야 합니다. array[p..q]와 array[q+1..r]에 있던 요소들이 안전하게 복사되기 전까지는 array[p..r] 위치에 덮어쓸 수 없습니다.

그러므로 merge 함수에서 우선 해야 하는 일은 두 임시 배열, lowHalf 와 highHalf를 만들고 array[p..q]의 모든 요소들을 lowHalf에, 또 array[q+1..r]의 모든 요소들을 highHalf에 복사하는 것입니다. lowHalf 의 크기는 얼마여야 할까요? 하위 배열 array[p..q]는 $q-p+1$‍개 요소를 포함하고 있습니다. highHalf의 경우는 어떨까요? 하위 배열 array[q+1..r]은 $r-q$‍ 개 요소를 포함하고 있습니다. (자바스크립트에서는 배열을 생성할 때 그 크기를 지정하지 않아도 됩니다. 그렇지만 다른 프로그래밍 언어에서는 크기를 지정해야 하기 때문에 알고리즘을 설명할 때 이를 고려하는 경우가 많습니다.)

배열 [14, 7, 3, 12, 9, 11, 6, 2]를 array[0..3] 과 array[4..7]을 재귀적으로 정렬하고($p=0$‍, $q=3$‍, $r=7$‍이 됨) 이 하위 배열들을 lowHalf와 highHalf에 복사하면 어떻게 되는지 나타냈습니다.

array 내 숫자들은 이 배열의 위치에는 값이 있지만 "진짜" 값은 현재 lowHalf와 highHalf에 있음을 나타내기 위해 회색으로 나타냅니다. 이제 회색으로 처리된 숫자들을 마음대로 덮어쓸 수 있습니다.

이제 lowHalf와 highHalf에 있는 정렬된 하위 배열을 array[p..r]로 병합해봅시다. 두 하위 배열에 있는 최솟값은 array[p]에 입력해야 합니다. 이 최솟값은 그럼 어디에 들어가야 할까요? 두 하위 배열이 모두 정렬되어 있기 때문에 최솟값은 반드시 lowHalf[0]나 highHalf[0] 둘 중 한 곳에는 존재해야합니다. (두 군데에 모두 같은 값이 입력되어 있을 수 있습니다. 이 때는 둘 중 아무 값이나 호출해도 됩니다.) 비교 한번만으로 lowHalf[0]나highHalf[0]둘 중 어느것을 array[p]에 입력해야 할지 판단할 수 있습니다. 위 예제에서는 highHalf[0] 값이 더 작습니다. 이제 배열 내 인덱스에 입력할 변수 세 개를 구축해봅시다.

lowHalf 또는 highHalf에서 array로 복사한 후 다음으로 작은 요소를 array의 다음 위치로 복사해 넣기 위해 k의 값을 하나 증가시킵니다. 또한 lowHalf에서 복사했다면 i의 값을 하나 증가시키고 highHalf에서 복사했다면 j의 값을 하나 증가시킵니다. 다음은 첫 번째 요소가 배열로 다시 복사되기 전과 후의 모습입니다.

highHalf[0]을 흐리게 처리하여 그 곳의 값을 더 이상 고려하지 않는다는 것을 나타냈습니다. highHalf 배열에서 병합되지 않은 부분은 현재 1의 값을 갖고 있는 j 인덱스에서 시작합니다. array[p]의 값은 이제 흐리게 되어 있지 않은데 이는 그 곳에 "실존"하는 값을 복사해 넣었기 때문입니다.

array에 다시 복사해 넣어야 할 다음 값은 어디에 있을까요? lowHalf (lowHalf[0]) 또는 highHalf (highHalf[1]) 중 하나에서 아직 선택되지 않은 첫 번째 요소입니다. 한 번의 비교로 lowHalf[0]가 더 작다는 것을 알 수 있으므로 이를 array[k]에 복사해 넣고 k와 i 값을 하나 증가시킵니다.

다음으로 lowHalf[1]와 highHalf[1]를 비교하여 highHalf[1]를 array[k]에 복사해야 하는지 결정합니다. 그런 다음 k와 j 값을 증가시킵니다.

lowHalf[i]와 highHalf[j]를 비교하고 두 값 중 더 적은 값을 array[k]에 복사한 후 i 또는 j 값을 하나 증가시키는 과정을 반복합니다.

결국 lowHalf 또는 highHalf 중 한 배열의 값이 array에 모두 복사되게 됩니다. 이 예에서는 highHalf의 모든 값이 복사될 때 lowHalf의 마지막 몇 몇 값이 남아 있습니다. lowHalf 또는 highHalf에서 아직 자리를 차지하지 않은 남은 요소들을 그냥 복사하고 이 과정을 끝냅니다.

$n$‍개의 요소를 병합하는데 모두 $\mathrm{\Theta }(n)$‍ 시간이 걸린다는 것과 걸리는 시간은 하위 배열의 크기와 비례한다는 것을 알아냈습니다. 이제 그 이유에 대해 알아봅시다. 병합에는 세 가지 부분이 있다는 것을 방금 배웠습니다:

위의 각 단계를 실행하려면 코드가 몇 줄이나 필요할까요? 요소 한 개당 일정한 수 만큼의 개수가 필요합니다. 각 요소는 1단계에서 정확히 한 번씩 배열에서 lowHalf 또는 highHalf 중 하나로 복사됩니다. 2단계에서의 비교는 일정한 시간이 소요됩니다. 이 단계에서는 두 요소만을 비교하고 각 요소는 최대 한 번만 비교에서 "이기게" 되기 때문입니다. 2단계와 3단계에서 각 요소는 정확히 한 번 array로 다시 복사됩니다. 코드 한 줄의 실행하는데 요소 당 일정한 시간이 걸리고 하위 배열 array[p..q]에는 $n$‍개의 요소가 있기 때문에 병합하는데 걸리는 실행 시간은 $\mathrm{\Theta }(n)$‍이 됩니다.

다음 심화문제에서는 이 선형 시간 병합을 구현해 보도록 하겠습니다. 두 심화문제를 합치면 완전한 병합 정렬 알고리즘을 구현할 수 있습니다.

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