2751번: 수 정렬하기 2

#include <stdio.h>

#include <string.h>

void merge(int *base, int n);

int num[1000000];

int main()

{// merge

int N;

scanf("%d", &N);

for (int i = 0; i < N; ++i)

scanf("%d", &num[i]);

merge(num, N);

for (int i = 0; i < N; ++i)

printf("%d\n", num[i]);

}

void merge(int *base, int n)

{

int left = n / 2, right = n - left, l = 0, r = left, i = 0, *copy;

if (n < 2) return;

merge(base, left);

merge(base + left, right);

copy = (int *)malloc(sizeof(int)*n);

memcpy(copy, base, sizeof(int)*n);

while ((l < left) && (r < n))

{

if (copy[l] <= copy[r])

base[i] = copy[l++];

else

base[i] = copy[r++];

++i;

}

while (l < left)

base[i++] = copy[l++];

while (r < n)

base[i++] = copy[r++];

free(copy);

}