Merge Sorting Algorithm.

1. 병합정렬은 이미 정렬된 두 파일을 병합(Merge)하는 과정을 일반화한 것이다. 또한 자료 배열에 접근하는 방법이 순차적(Sequential)이다. 다른 정렬 방법이 뚝 떨어진 배열 요소를 비교하고 교환하는데 비하여 병합정렬은 배열을 차례로 읽으면서 비교하는 방법이다.
그래서 병합정렬은 연결 리스트와 같은 순차적 접근만이 가능한 자료 구조에 유일한 정렬방법이 된다.

2. 두 개의 배열에서 꺼내어지는 최소의 값들을 비교하여 작은 쪽의 값을 선택하는 방법으로 이루어진다. 또한 병합에서는 반드시 한 쪽이 먼저 소진되는 경우가 발생하므로 이에 대한 대비도 있어야 한다.

void merge_sort(int a[], int n)
{
int i, j, k, first, second, size;
int *b;

b = new int[n]; //병합 장소

for (size = 1; size < n; size++)
{
first = -2 * size; //first와 second의 초기값
second = first + size;

while (second + size * 2 < n) //다음 second값이 n보다 작으면
{
first = second + size;
second = first + size;

i = first;
j = second;
k = first;

while (i < first + size || (j < second + size && j < n))
{ //병합이 완료되지 않았다면
if (a[i] <= a[j])
{
if (i < first+size)
b[k++] = a[i++];
else
b[k++] = a[j++];
}
else
{
if (j < second + size && j < n)
b[k++] = a[j++];
else
b[k++] = a[i++];
}
}
}
for (i = 0; i < n; i++)
a[i] = b[i];
}
delete b;
}

3. 병합정렬의 루프와 쉘 정렬의 루프는 상당히 비슷하다. 쉘 정렬은 h를 점점 감소시킴에 반해서 병합정렬은 단위의 크기를 증가시켜야 하는 점이 다르지만 루프의 조건이 상당히 비슷하다.

4. 소스를 보면 알겠지만, 루프문의 중복 사용으로 size를 하나씩 증가시키는데, size만큼 블럭을 이동해야 하므로 '*'연산을 하여 1,2,4,8,16... 순서로 블럭을 이동한다., 이전 블럭은 이미 정렬이 이루어진 상태이므로 각 블럭의 최초값부터 하나씩 비교하면서 작은 값을 선택하여 새로운 배열에 삽입한다.
중요한 점은, 1 5 8 11 이라는 A배열과 13 15 18 19 라는 B배열이 있다고 가정했을때, A배열의 모든 원소는 B배열의 첫번째 원소인 13보다 작다. 그러므로 A배열의 모든 원소가 소진될 때 까지 B배열의 값은 하나도 선택되지 않는다. 그러므로 루프문 내의 조건에서 둘 중 하나의 원소가 바닥났을 때의 경우를 생각하여, 비교할 원소가 없을 때에는 남은 원소를 차례로 선택하도록 해 주는 작업이 필요하다.