07/07/16 02:00:27
>>2 とりあえず関数だけ
#include <stdlib.h>
#include <string.h>
void arraycopy (int n, int *dst, int *src) {
memcpy (dst, src, sizeof(int)*n);
}
void mergesort (int n, int *a) {
int *b = calloc (n, sizeof(int)); /* temporal space */
int s = 1; /* segment size */
arraycopy (n, b, a);
while (s < n) {
int f; /* start of segments pair */
for (f = 0; f < n; f += 2*s) {
/* merge two segments b[f : f+s], b[f+s : f+2s] into a[f : f+2s] */
int i, i1, i2;
i = i1 = i2 = 0;
while (i1 != s || i2 != s) {
if (i2 == s || i1 != s && b[f+i1] <= b[f+s+i2]) {
a[f+i++] = b[f+i1++];
} else {
a[f+i++] = b[f+s+i2++];
}
}
}
arraycopy (n, b, a); /* copy a to b */
s *= 2;
}
free (b);
}