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

/**
 * split (nums, size, left, lsize, right, rsize)
 *   Split an array into two parts.
 */
void
split (int nums[], int size, int left[], int lsize, int right[], int rsize)
{
  int i;
  for (i = 0; i < lsize; i++)
    left[i] = nums[i];
  for (i = lsize; i < size; i++)
    right[i-lsize] = nums[i];
} // split

/**
 * merge two sorted arrays back together.
 */
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 ((lp < lsize) && (rp < rsize))
    nums[np++] = (left[lp] < right[rp]) ? left[lp++] : right[rp++];
  while (lp < lsize)
    nums[np++] = left[lp++];
  while (rp < rsize)
    nums[np++] = right[rp++];
} // merge

/**
 * merge_sort (nums, size)
 *   Sort the array using the merge-sort routine.
 */
int
merge_sort (int nums[], int size)
{
  int lsize = size/2;
  int rsize = size - lsize;
  int left[lsize];
  int right[rsize];

  if (size <= 1)
    return size;

  split (nums, size, left, lsize, right, rsize);
  merge_sort (left, lsize);
  merge_sort (right, rsize);
  merge (nums, size, left, lsize, right, rsize);

  return lsize + rsize;
} // merge_sort