[알고리즘] 합병 정렬 (The divide-and-conquer)

일명 합병 정렬은 merge sort로 잘 알려져 있으며 분할 정복 방식의 정렬 알고리즘이다.

divide: 주어진 문제를 작은 문제로 분할한다.
conquer: 작은 문제를 순환적으로 처리. 즉 더 작은 소문제의 순환이 없을때까지..
merge: 작은 문제에 대한 해를 합병하여 원래 문제에 해를 구한다.

다음 그림은 Introduction to Algorithms에 나와 있는 그림으로써 합병정렬의 모습을
보여 준다.

알고리즘의 Pseudu code는 다음과 같다.

MERGE(A, p, q, r)
1  n₁ ← q - p + 1
2  n₂ ← r - q
3  create arrays L[1 ‥ n₁ + 1] and R[1 ‥ n₂ + 1]
4  for i ← 1 to n₁
5       do L[i] ← A[p + i - 1]
6  for j ← 1 to n₂
7       do R[j] ← A[q + j]
8  L[n₁ + 1] ← ∞
9  R[n₂ + 1] ← ∞
10  i ← 1
11  j ← 1
12  for k ← p to r
13       do if L[i] ≤ R[j]
14             then A[k] ← L[i]
15                  i ← i + 1
16             else A[k] ← R[j]
17                  j ← j + 1


오늘 이를 바탕으로 오래간만에 프로그래밍을 해 보았다. 좀 엉성하기는 하지만 그래도 나름대로
잘 돌아가는 것 같다.

merge_sort.c