#include <stdio.h>
#include <stdlib.h>

static int *tempArr; // 병합 결과를 일시적으로 저장하는 배열

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++)
tempArr[p++] = a[i]; // 앞부분을 buff에 임시로 저장, i는 계속 증가
while (i <= right && j < p)
// buff에 존재하는 a의 앞부분과 a의 뒷부분을 비교해서 a에 넣어줌
// i = center + 1 인 상황
// a가 전부 들어가면 i <= right 조건에 의해 반복문이 끝남
// buff가 전부 들어가면 j < p 조건에 의해 반복문이 끝남
a[k++] = tempArr[j] <= a[i] ? tempArr[j++] : a[i++];

while (j < p) // buff에 남아있는 요소를 a에 차례로 넣어준다
a[k++] = tempArr[j++];
}
}

int mergeSort(int a[], int n)
{
tempArr = calloc(n, sizeof(int)); // 병합 결과를 일시적으로 저장하는 배열
if (tempArr == NULL)
return -1;

__mergesort(a, 0, n - 1);

free(tempArr);

return 0;
}

int main(void)
{
int i, nx;
int *x;
puts("병합 정렬");
printf("요소 개수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));

for (i = 0; i < nx; i++)
{
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}

mergeSort(x, nx);

puts("오름차순으로 정렬했습니다.");
for (i = 0; i < nx; i++)
printf("x[%d] = %d\n", i, x[i]);

free(x);

return 0;
}