/**
 * mergesort.c
 */

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

/**
 * 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;
}