Page 253 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

__mergesort 함수는 a(정렬할 배열), left, right(첫 번째, 마지막 요소의 인덱스)를 인자로 전달받

으며 left가 right보다 작을 때 동작합니다. 가장 먼저 앞부분(a[left] ~ a[center])과 뒷부분
(a[center + 1] ~ a[right])에 대해서 __mergesort 함수를 재귀 호출합니다. 그런 다음 그림
6-31처럼 배열의 앞부분과 뒷부분은 정렬을 마치게 됩니다.

__mergesort(int a[], int left, int right);

left center right
1 3 12 6 4 11 8 7 3 2 6 5
__mergesort(a, left, center); __mergesort(a, center + 1, right);
 
1 3 4 6 11 12 2 3 5 6 7 8
재귀 호출로 앞부분을 정렬합니다. 재귀 호출로 뒷부분을 정렬합니다.

[그림 6-31] 앞부분과 뒷부분의 정렬
__mergesort 함수가 재귀적으로 여러 번 호출되어 정렬을 마칩니다.

정렬을 마친 앞부분과 뒷부분의 병합은 작업용 배열 buff를 사용합니다. 병합을 수행하는 코
드는 아래와 같습니다.

for(i = left; i <= center; i++)
1
buff[p++] = a[i];
while(i <= right && j < p)
2
a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];
while(j < p)
3
a[k++] = buff[j++];

병합 순서는 그림 6-32와 같이 3단계로 이루어집니다.

1 배열의 앞부분(a[left] ~ a[center])을 buff[0] ~ buff[center – left]로 복사합니다. for문이 끝날 때
p의 값은 복사한 요소의 개수 center – left + 1이 됩니다( a ).
2 배열의 뒷부분(a[center + 1] ~ a[right])과 buff로 복사한 배열의 앞부분 p개를 병합한 결과를 배열 a
에 저장합니다( b ).
3 배열 buff에 남아 있는 요소를 배열 a로 복사합니다( c ).

06•정렬 253