[대학교 알고리즘] MergeSort

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_OR_KEYS]; // 퀵정렬에는 없지만 합병정렬에만 있는 합병을 하기 위한 배열.
int i, LeftPtr, RightPtr, BufPtr;
LeftPtr = Low; // 왼쪽
RightPtr = Mid +1; // 반을 나누기 위해 가운데
BufPtr = Low; // 이것도 왼쪽
while (LeftPtr <= Mid && RightPtr <= High) //
if (A[LeftPtr] < A[RightPtr])
B[BufPtr++] = A[LeftPtr++];
else B[BufPtr++] = A[RightPtr++];
if (LeftPtr > Mid)
for (i=RightPtr; i<=High; i++)
B[BufPtr++] = A[i];

else
for (i=LeftPtr; i<=Mid; i++)
B[BufPtr++] = A[i];
for (i=Low; i<=High; i++)
A[i] = B[i];
}

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