(오름차순 기준)
배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬을 수행하는 알고리즘
병합 정렬 알고리즘
배열의 요소 개수가 2개 이상인 경우
/* 오름차순 병합 정렬 프로그램 */
static int* buff; /* 작업용 배열 */
/*--- 병합 정렬(main 부분) ---*/
static void __mergesort(int a[], int left, int right)
{
if (left < right) {
int center = (left + right) / 2;
int p = 0;
int i;
int j = 0;
int k = left;
__mergesort(a, left, center); /* 앞부분에 대한 병합 정렬 */
__mergesort(a, center + 1, right); /* 뒷부분에 대한 병합 정렬 */
for (i = left; i <= center; i++)
buff[p++] = a[i];
while (i <= right && j < p)
a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];
while (j < p)
a[k++] = buff[j++];
}
}
/*--- 병합 정렬 함수 ---*/
int mergesort(int a[], int n)
{
if ((buff = calloc(n, sizeof(int))) == NULL)
//병합한 결과를 일시적으로 저장할 작업용 배열 buff 생성
return -1;
__mergesort(a, 0, n - 1); /* 배열 전체를 병합 정렬 */
free(buff);
return 0;
}
for (i = left; i <= center; i++)
buff[p++] = a[i];
while (i <= right && j < p)
a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];
while (i <= right && j < p)
a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];