병합 정렬 : sorting 된 두 배열을 합치면서 해결한다.

 병합 정렬 (merge sort)는, 분할을 하고, 정복하는 단계에서 정렬된 두 배열을 합치는 식으로 동작합니다. 추가적인 공간이, 배열 크기만큼 필요하다는 것을 생각해 본다면, 메리트가 없을 수도 있어요. 실제로, Quick이 merge보다 빠르다는 이야기도 있을 정도이니까요.

 

 그런데, Quick이 최악의 경우에 제곱에 비례하는 시간이 걸리는 반면에, merge는 그렇지 않아요. depth가 logn이기 때문입니다. 실제로 머지는 최악이던 최선이던 O(nlogn)에 동작합니다. 버블이나, insertion, selection sort에 비하면 꽤 빠릅니다.

 

 

---

 일단 정렬이 된 두 부분 배열이 있다고 해 봅시다. 즉, le에서 mid까지 정렬이 되어 있고, mid+1부터 ri까지 sorting이 되어 있습니다. 이 때, le에서 ri까지 sort를 하려면 어떻게 해야 할까요?

 

 

 초록색으로 칠한 왼쪽 배열과, 보라색으로 칠한 오른쪽 배열이 있습니다. 이 둘은 정렬이 되어 있는 상태입니다. 이것으로부터 left_s부터 right_e까지 어떻게 오름차순으로 좌르륵 좌르륵 나오게 할까요? 일단 초록색의 시작 위치를 le, 보라색의 시작 위치를 ri라고 해 봅시다.

 

 

 우리는 brr에 left_s부터 right_e까지 정렬한 결과를 넣을 겁니다. 그리고, 그 결과를 다시 arr에 복사할 거에요. 알고리즘 자체는 간단합니다. arr[le]가 arr[ri]보다 작거나 같으면, arr[le]의 값을 배열 brr에 넣습니다. 그리고 le는 다음 원소를 가리킵니다.

 

 그렇지 않다면 arr[ri]의 값을 brr에 넣습니다. 그리고 ri는 다음 원소를 가리키게 합니다. 천천히 봅시다.

 

 

 먼저 le가 가리키는 건 연두색으로, ri가 가리키는 건 보라색으로 표시해 놓았습니다. 2가 3보다는 작거나 같습니다. 따라서, 2가 brr에 먼저 들어가고, le를 하나 증가시킵니다. 그러면, le가 4를 가리킬 겁니다.

 

 

 다음에 arr[le]와 arr[ri]를 compare 했더니, 오른쪽 것이 더 작습니다. 그러면 3을 넣어야 될 겁니다. brr에. 그리고 ri의 값을 하나 증가시킵니다.

 

 

 그 다음에 봅시다. 연두색으로 칠해진 왼쪽 값은 4입니다. 보라색으로 칠해진 우측 값 또한 4입니다. 두 값이 같아요. merge sort는 stable한 특성을 가지고 있는데요. 우선 순위가 같은 경우, 순서가 바뀌지 않는다는 특성을 가지고 있습니다.

 

 왼쪽과 오른쪽 것이 같은 경우에는 왼쪽 것을 넣고, le 포인터를 하나 증가시킵니다.

 

 

 다음에 15와 4를 비교해 봅니다. 오른쪽 것이 더 작습니다. 따라서, arr[ri]의 값을 brr에 넣습니다.

 

 

 다음에 15와 7을 비교합니다. 역시 7이 작습니다. 따라서, 오른쪽 것을 넣습니다.

 

 

 보라색, 그러니까 오른쪽 부분은 다 넣었습니다. ri가 right_e보다 커졌거나, le가 left_e보다 커졌습니다. 그렇기 때문에, 일단 빠져 나옵니다. 빠져 나오고, 어떻게 해야 할까요?

 

 

병합 정렬 과정에서 남은 연두색 부분.

 le는 아직 left_e보다 커지지 않았습니다. 따라서, 나머지 왼쪽 부분을 모두 넣어야 합니다. 이것은 while이나 for 루프로 처리하거나, memcpy로 처리하실 수 있습니다. 만약에 보라색 부분이 남았다면, 즉, ri가 right_e보다 커지지 않았다면, 보라색 부분도 brr에 차례대로 넣으면 됩니다.

 

 

---

 이제 2751번 수 정렬하기 2를 chogahui05로 낸 코드를 봅시다.

 

 

 먼저, 반씩 쪼개서 들어가고 있어요. 21, 22번째 줄을 보면, 부분 문제를 거의 절반으로 쪼개서 해결한 뒤에, 23번째 줄인, conquer를 호출하고 있음을 알 수 있습니다.

 

 

 그러면 여기서 무엇을 할까요? 제가 설명했던 알고리즘을 수행합니다. 정렬된 두 배열을 merge 하기만 합니다. 36번째 loop와 38번째 loop는 큰 for문을 돌고 나서, 아직 정렬이 되지 않은 원소들을 순회하면서 brr에 넣기 위해서 있는 코드입니다.

 

 이렇게 brr이 정렬 되었다면, 다시 arr로 복사하면 될 겁니다. 이 부분은 memcpy나 memmove 등으로 빠르게 수행할 수 있습니다.

 

 

 그런데, 보통은, sub problem에서, 정렬해야 하는 배열의 크기가 32 이하인 경우에, merge를 하지 않고, 곧바로 insert sort를 하는 것을 알 수 있습니다. 이것은, 작은 배열에서는 오히려 병합 정렬보다 insertion이 빠르기 때문입니다.