/**
 * mergesort.c - An implementation of the legendary merge sort routine.
 */

/**
 * Procedure:
 *   split
 * Parameters:
 *   nums, an array of integers
 *   size, an integer.
 *   left, an array of integers
 *   lsize, an integer
 *   right, an array of integers
 *   rsize, an integer
 * Purpose:
 *   Split the first size elements nums into two arrays, left and right.
 * Produces:
 *   [Nothing; Called for the side effects.]
 * Preconditions:
 *   nums contains at least size elements.
 *   left contains at least lsize elements.
 *   right contains at least rsize elements.
 *   size = lsize + rsize.
 * Postconditions:
 *   nums is unmodified
 *   nums[0..size-1] is a permutation of the combination of
 *     left[0..lsize-1] and right[0..rsize-1]
 */
void
split (int nums[], int size, int left[], int lsize, int right[], int rsize)
{
  int i;
  // Copy elements into the left half
  for (i = 0; i < lsize; i++)
    left[i] = nums[i];
  // Copy elements into the right half
  for (i = lsize; i < size; i++)
    right[i-lsize] = nums[i];
} // split

/**
 * Procedure:
 *   merge
 * Parameters:
 *   nums, an array of integers
 *   size, an integer.
 *   left, an array of integers
 *   lsize, an integer
 *   right, an array of integers
 *   rsize, an integer
 * Purpose:
 *   Merge two sorted arrays into a larger sorted array.
 * Produces:
 *   [Nothing; Called for the side effects.]
 * Preconditions:
 *   nums contains at least size elements.
 *   left contains at least lsize elements.
 *   right contains at least rsize elements.
 *   size = lsize + rsize.
 *   The elements in left are in order.  That is, left[i] <= left[i+1]
 *     for all reasonable i.
 *   The elements in right are in order.  That is, right[i] <= right[i+1]
 *     for all reasonable i.
 * Postconditions:
 *   left is unmodified
 *   right is unmodified
 *   nums[0..size-1] is a permutation of the combination of
 *     left[0..lsize-1] and right[0..rsize-1]
 *   The elements in nums are in order.  That is, nums[i] <= nums[i+1]
 *     for all reasonable i.
 */
void
merge (int nums[], int size, int left[], int lsize, int right[], int rsize)
{
  int lp = 0;	// Pointer into the left array
  int rp = 0;	// Pointer into the right array
  int np = 0;	// Pointer into main array

  // While elements remain in both subarrays
  while ((lp < lsize) && (rp < rsize))
    // Copy the smallest remaining element into nums
    nums[np++] = (left[lp] < right[rp]) ? left[lp++] : right[rp++];

  // Copy all remaining elements from left into nums
  while (lp < lsize)
    nums[np++] = left[lp++];

  // Copy all remaining elements from right into nums
  while (rp < rsize)
    nums[np++] = right[rp++];
} // merge

/**
 * Procedure:
 *   merge_sort
 * Parameters:
 *   nums, an array of integers
 *   size, an integer.
 * Purpose:
 *   Sort nums using the merge-sort algorithm.
 * Produces:
 *   result, the size of the array.  (A pointless value)
 * Preconditions:
 *   nums contains at least size elements.
 * Postconditions:
 *   nums is a permutation of the original array.
 *   The elements in nums are in order.  That is, nums[i] <= nums[i+1]
 *     for all reasonable i.
 */
int
merge_sort (int nums[], int size)
{
  int lsize = size/2;		// The size of the left half
  int rsize = size - lsize;	// The size of the right half
  int left[lsize];		// The left half
  int right[rsize];		// The right half

  // Arrays with 0 or 1 elements are already sorted.
  if (size <= 1)
    return size;

  // Copy elements into the two subarrays
  split (nums, size, left, lsize, right, rsize);

  // Sort the two subarrays
  merge_sort (left, lsize);
  merge_sort (right, rsize);

  // And join them back together
  merge (nums, size, left, lsize, right, rsize);

  // We're done
  return size;
} // merge_sort