이 첨부 파일에 있는 건 일반적인 함수의 형태이다. (int형 뿐 아니라 모든 형태의 자료형을 비교할 수 있도록 만든 것이다)
자료 배열의 선두 번지인 base,
자료의 개수 nelem,
레코드의 크기 width,
키값의 비교를 하는 함수 포인터 fcmp 를 뜻한다.
fcmp 함수는
int intcmp(const void *a, const void *b) 등을 뜻한다.


■ 병합 정렬 개념

이미 순서적으로 배열된 두 개의 파일에서 레코드의 배열 순서에 따라 차례로 한 레코드씩 가져다 비교하여 작은 키 값을 가지는 레코드를 새로운 병합 파일에 출력하고, 작은 레코드를 가져온 파일에서 다음 순서의 레코드를 가져와 이전에 비교한 큰 키 값을 가진 레코드와 비교하는 과정을 반복 수행하므로 완전히 순서적으로 배열된 한 개의 파일을 만드는 것을 의미
병합 정렬(merge sort:합병 정렬)은 퀵 정렬과 마찬가지로 분할 정복 방식의 알고리즘
퀵 정렬에서는 분할되는 두 부분배열의 크기가 다를 수도 있고 이것 때문에 최악의 성능이 O(n2)으로 되었는데 병합 정렬에서는 두 부분배열의 크기가 항상 같게 분할 됨.
병합 정렬의 수행시간은 최악의 경우에도 O(NlogN)
병합 정렬은 별도의 임시 기억장소(배열)가 필요
실제로는 수행시간이 많이 걸리며, 외부정렬에 주로 활용


■ 병합 정렬 방법

병합 정렬은 전형적인 분할 정복 방법의 예
분할 정복 방법은 순환적으로 문제를 푸는 방법으로서 주어진 문제를 여러 개의 소문제로 분할하여 이 소문제를 순환적으로 푼 후 이들의 해를 결합하여 원래 문제의 해를 구하는 방식
즉, 순환 호출시 마다 다음과 같은 세 단계의 작업이 이루어짐
▷ 분할 : 주어진 문제를 여러 개의 소문제로 분할한다.

▷ 정복 : 소문제들을 순환적으로 처리하여 정복한다.
              만약 소문제의 크기가 충분히 작다면 순환 호출없이 소문제에 대한 해가 구해진다.

▷ 합병 : 소문제에 대한 해를 합병하여 원래 문제의 해를 구한다.

병합 정렬 알고리즘을 분할 정복 방법의 세 단계로 대응 시켜 보면 다음과 같음
① 분할 : 정렬할 n원소의 배열을 n/2 원소의 두 부분배열로 분할한다.

② 정복 : 두 부분배열에 병합 정렬을 각각 순환적으로 적용하여 두 부분배열을 정렬한다.

③ 합병 : 두 정렬된 부분배열을 머지하여 원래의 정렬된 배열을 만든다.



■ 머지 방법

두 정렬된 부분배열의 원소를 비교, 결합하여 하나의 정렬된 배열을 만든다.
두 부분 배열은 서로 인접하여 있으며 머지된 결과는 제자리에 남는다.
두 부분배열은 서로 인접하여 있기 때문에 이들의 위치를 표현하는데는 그들이 속해있는 배열명과 첫째 부분배열의 시작점과 끝점 그리고 두 번째 부분배열의 끝점을 나타내는 배열 첨자만 필요 (예) A[1:3]과 A[4:6]을 머지하려면 배열의 이름인 A와 첨자인 1,3,6만을 함수 Merge에 전달하면 됨
두 개의 부분배열을 머지하는 데는 그 두 부분배열을 합한 것만큼의 여분의 메모리 공간이 필요
- 배열 B가 그 여분 공간으로 사용됨


■ 병합 정렬 과정    

10개의 키가 있는 배열에 병합 정렬을 적용하는 과정을 보임
단계 1에 정렬하고자 하는 배열이 있음
단계 2~5에서는 MergeSort가 호출되어 각 단계마다 배열이 이분됨
단계 6~9에서는 함수 Merge가 호출되어 부분배열이 두 개씩 머지됨을 알 수 있음
각 경로에 붙어 있는 레이블은 병합 정렬 과정에서 취해지는 일의 순서를 나타냄
실제로 단계 1~5에 있는 레이블은 함수 MergeSort가 순환적으로 호출되는 순서이고,
단계 6~9의 레이블은 함수 Merge가 호출되어 행한 일을 나타냄


■ 병합 정렬 알고리즘
-------------------------------------------------------------------------------
   void MergeSort(int A[ ], int Low, int High) /* 입력: A[Low:High] - 정렬하려는 배열 */
   /* Low, High - 정렬할 원소가 있는 곳을 나타내는 최소, 최대 인덱스 */
   /* 출력: A[Low:High] - 정렬된 배열 */
       {              
              int Mid;    
/*a*/    if(Low < High)
              {
/*b*/           Mid = (Low + High)/2;
/*c*/           MergeSort(A[ ], Low, Mid);
/*d*/           MergeSort(A[ ], Mid+1, High);
/*e*/           Merge(A[ ], Low, Mid, High);
               }
       }  

ⓐif문은 '배열 원소가 둘 이상이면'의 의미를 나타냄 ⓑ둘 이상이면 그 배열의 중간위치를 구하고
ⓒ분할된 왼쪽의 부분배열에 대하여 MergeSort를 순환 호출하여 정렬하고, 왼쪽 부분배열의 정렬이 끝났으면
ⓓ오른쪽 부분배열에 대하여 MergeSort를 순환
호출하여 오른쪽 부분배열을 정렬함
ⓔ왼쪽과 오른쪽이 끝났으면 이들을 Merge함

/*  병합 정렬 알고리즘 */

   void Merge(int A[ ], int Low, int Mid, int High)
   /* 입력: A[Low:Mid], A[Mid+1:High] - 정렬된 두 배열 */
   /* 출력: A[Low:High]-A[Low:Mid]와 A[Mid+1:High]를  합병하여 정렬된 배열 */
             {
                  int B[NUM_OF_KEYS];
                  int i, LeftPtr, RightPtr, BufPtr;
/*1*/        LeftPtr = Low; RightPtr = Mid + 1; BufPtr = Low;
/*2*/        while(LeftPtr <= Mid && RightPtr <= High)
/*3*/               if(A[LeftPtr] < A[RightPtr])
/*4*/                    B[BufPtr++] = A[LeftPtr++];    
/*5*/               else B[BufPtr++] = A[RightPtr++];
/*6*/         if (LeftPtr > Mid)
/*7*/               for (i = RightPtr; i <= High; i++)
/*8*/                    B[BufPtr++] = A[i];
                 else    
/*9*/             for (i=LeftPtr; i <= Mid; i++)
/*10*/                  B[BufPtr++] = A[i];
/*11*/       for (i = Low; i <= High; i++)
/*12*/            A[i] = B[i];            
             }

②③④⑤줄의 while 루프는 머지가 진행되고 있는 두 부분배열 모두에 아직 키가 남아 있을 때, 이들을 머지

⑥⑦⑧⑨⑩줄의 if문은 두 부분배열 중에서 한 개의 배열에만 키가 남아 있을 때 이 키들을 배열 B의 머지된 원소들 뒤에 그대로 복사하는 일

⑪⑫ for루프는 머지가 끝나면 배열 B에 있는 정렬된 키들을 배열 A에 옮기는 일을 담당
-------------------------------------------------------------------------------



■ 병합 정렬 분석
▷ 원소의 개수가 각각 m,n인 두 배열을 합병하기 위하여는 최악의 경우에 m+n-1회의 비교
▷ 두 부분 배열의 크기가 같고 이를 m이라 할 때, 최악의 경우에 2m-1회의 비교
▷ n개의 원소로 구성된 배열에 병합 정렬을 적용하면 그 실행 시간은 n/2개의 원소로 된
           두 개의 부분 배열을 정렬하는 시간과 이들을 합병하는 데 드는 시간의 합으로 O(nlogn)
▷ 병합 정렬에서는 동일한 두 키의 상대 위치가 정렬 과정에서 변하지 않으므로 안정적이나,
           합병하는 과정에서 입력 배열의 크기만큼의 메모리 공간이 요구되므로 제자리 정렬은 아님
▷ 최악의 경우의 실행시간이 이지만 각 부분배열을 합병 과정에서 합병된 결과가 배열 B에서
           배열 A로 항상 복사되어야 하는 단점