#include "mergesort.h" #include #include /* Sorts int array a[0..n-1] */ void mymergesort(int a[], int n) { int *buffer = malloc(n * sizeof(int)); /* helper array */ div_merge(a, buffer, 0, n-1); free(buffer); } /* Sorts int array a[low..hi] using the int array buffer[]. */ void div_merge(int a[], int buffer[], int low, int hi) { if (low >= hi) return; /* done */ int middle = (low + hi) / 2; div_merge(a, buffer, low, middle); div_merge(a, buffer, middle + 1, hi); merge(a, buffer, low, middle, hi); /* merge the two sorted sub-arrays */ } /* Merges a[low..mid] and a[mid+1..hi] into b[low..hi] and copies back to a[low..hi]. */ void merge(int a[], int b[], int low, int mid, int hi) { int i, i1 = low, i2 = mid + 1; for (i = low; i <= hi; i++) { if (i1 > mid) b[i] = a[i2++]; else if (i2 > hi) b[i] = a[i1++]; else if (a[i1] < a[i2]) b[i] = a[i1++]; else b[i] = a[i2++]; } /* copy everything back from b to a */ for (i = low; i <= hi; i++) a[i] = b[i]; } int main(void) { int[100] array; int n = 0; while (scanf("%d", &array[n]) == 1) n++; mymergesort(array, n); int i; for (i = 0; i < n; i++) printf("%d ", array[i]); printf("\n"); return n; }