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

０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１
5 6 4 8 3 7 9 0 1 5 2 3
앞부분과 뒷부분으로 나눈 부분 5 6 4 8 3 7 9 0 1 5 2 3
을 각각 정렬합니다.  정렬  정렬
3 4 5 6 7 8 0 1 2 3 5 9
병합
정렬을 마친 배열의 모습입니다. 0 1 2 3 3 4 5 5 6 7 8 9
[그림 6-29] 병합 정렬 과정

이때 앞뒤에 놓인 6개의 요소를 정렬할 때는 그냥 정렬 ６ ７ ８ ９ 10 11
9 0 1 5 2 3
하는 것이 아니라 다시 병합 정렬을 적용합니다. 예를
들어 뒷부분은 오른쪽 그림처럼 정렬합니다. 물론 이 9 0 1 5 2 3
 정렬  정렬
과정에서 만들어지는 앞부분({9, 0, 1})과 뒷부분({5, 2, 0 1 9 2 3 5
3})도 같은 순서에 따라 정렬합니다.
병합
0 1 2 3 5 9

[그림 6-30] 뒷부분의 정렬
병합 정렬 알고리즘
병합 정렬 알고리즘의 순서를 정리하면 다음과 같습니다.

배열의 요소 개수가 2개 이상인 경우
1. 배열의 앞부분을 병합 정렬로 정렬합니다.
2. 배열의 뒷부분을 병합 정렬로 정렬합니다.
3. 배열의 앞부분과 뒷부분을 병합합니다.

실습 6-14는 병합 정렬 프로그램입니다.

실습 6-14 •완성 파일 chap06/merge.c
01 /* 병합 정렬 프로그램 */
02 #include <stdio.h>
03 #include <stdlib.h>
04
05 static int *buff; /* 작업용 배열 */
06
07 /*--- 병합 정렬(main) ---*/
08 static void __mergesort (int a[], int left, int right)
09 {

250 C 알고리즘