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

06-7 병합 정렬

병합 정렬은 배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하
여 정렬을 수행하는 알고리즘입니다.

정렬을 마친 배열의 병합
먼저 정렬을 마친 두 배열의 병합(merge)을 살펴보겠습니다. 각 배열에서 선택한 요소의 값을

비교하여 작은 값의 요소를 꺼내 새로운 배열에 넣는 작업을 반복하여 정렬을 마치는 배열을
만듭니다. 실습 6-13은 이 과정을 수행하는 프로그램입니다. merge 함수는 요소의 개수가
na개인 배열 a와 요소의 개수가 nb개인 배열 b를 병합하여 배열 c에 저장합니다.

a １ ２ ３ ４ ５
2 4 6 8 11 13
b １ ２ ３ ４ ５ ６
1 2 3 4 9 16 21
a와 b 배열을 비교하여 작은 c １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ １２
값을 꺼내 c에 넣습니다. 1 2 2 3 4 4 6 8 9 11 13 16 21

[그림 6-28] 정렬을 마친 배열의 병합

배열 a, b, c를 스캔할 때 선택한 요소의 인덱스는 pa, pb, pc입니다. 이 인덱스를 저장한 변수
를 지금부터 커서라고 하겠습니다. 처음에는 첫 요소를 선택하므로 커서를 모두 0으로 초기
화합니다(●으로 표시).

다음은 실습 6-13에 표시한 번호와 그림 6-28에 대한 설명입니다.
설명을 먼저 읽은 다음에 코드를 보면서 의미를 다시 생각해 보세요.

1 배열 a에서 선택한 요소(a[pa])와 배열 b에서 선택한 요소(b[pb])를 비교하여 작은 값을
c[pc]에 저장합니다. 그런 다음 커서 pb, pc를 한 칸 옮기고 커서 pa는 그대로 둡니다. 그림
6-28을 예로 들면 b[0]의 1이 a[0]의 2보다 작으므로 c[0]에 대입하는 값은 1입니다.

커서 pa, pb가 가리키는 값을 비교하여 작은 값을 c[pc]에 대입하고 커서 pa, pb, pc를 진행
하는 작업을 반복합니다. 커서 pa가 배열 a의 끝에 다다르거나 커서 pb가 배열 b의 끝에 다다
르면 이 작업을 종료합니다.

06•정렬 247