/** * mergesort.c */ #include #include /** * Pre: * Size of result is at least lsize + lsize. * Process: * */ void merge (int left[], int lsize, int right[], int rsize, int result[]) { int l = 0; // Index into left array int r = 0; // Index into right array int i = 0; // Index into result array while ((l < lsize) && (r < rsize)) // Compare the first remaining element in each subarray if (left[l] <= right[r]) result[i++] = left[l++]; else result[i++] = right[r++]; // We've run off of one of the arrays. We need to fill in the // remaining values in the other array. while (l < lsize) result[i++] = left[l++]; while (r < rsize) result[i++] = right[r++]; } // merge void mergesort (int values[], int size) { int i; int spare[size]; int lsize = size/2; // Integer division floors int rsize = size - size/2; // Base case: When don't we have to recurse? When do we know that // it's already sorted? if (size <= 1) return; // Copy values for convenience for (i = 0; i < size; i++) spare[i] = values[i]; // Split into two halves and sort each half mergesort (spare, lsize); mergesort (spare+lsize, rsize); // Merge them together, putting the results back into the original // array merge (spare, lsize, spare+lsize, rsize, values); } // mergesort int main (int argc, char *argv[]) { int size = argc-1; int values[argc]; int i; for (i = 0; i < size; i++) values[i] = atoi(argv[i+1]); mergesort(values, size); for (i = 0; i < size; i++) printf ("%3d ", values[i]); printf ("\n"); return 0; }