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

// +---------+--------------------------------------------------------
// | Headers |
// +---------+

#include "sort.h"


// +---------+--------------------------------------------------------
// | Helpers |
// +---------+

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

/**
 * Procedure:
 *   merge
 * Parameters:
 *   vals, an array of pointers
 *   size, an integer.
 *   left, an array of pointers
 *   lsize, an integer
 *   right, an array of pointers
 *   rsize, an integer
 *   comp, a comparator
 * Purpose:
 *   Merge two sorted arrays into a larger sorted array.
 * Produces:
 *   [Nothing; Called for the side effects.]
 * Preconditions:
 *   vals 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, 
 *     comp(left[i],left[i+1]) <= 0 for all reasonable i.
 *   The elements in right are in order.  That is, 
 *     comp(right[i],right[i+1]) <= for all reasonable i.
 * Postconditions:
 *   left is unmodified
 *   right is unmodified
 *   vals[0..size-1] is a permutation of the combination of
 *     left[0..lsize-1] and right[0..rsize-1]
 *   The elements in vals are in order.  That is, 
 *     comp(vals[i], vals[i+1]) <= 0 for all reasonable i.
 */
void
merge (void *vals[], int size, 
       void *left[], int lsize, 
       void *right[], int rsize,
       int (*comp)(const void *, const void*))
{
  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 vals
    vals[np++] = (comp (left[lp], right[rp]) < 0) ? left[lp++] : right[rp++];

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

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

// +--------------------+---------------------------------------------
// | Exported Functions |
// +--------------------+

void
sort (void *vals[], int start, int finish, 
      int (*comp)(const void *, const void*))
{
  int size = 1 + finish - start;// The size of the subarray to sort
  void *subvals = vals + start;	// The subarray 
  int lsize = size/2;		// The size of the left half
  int rsize = size - lsize;	// The size of the right half
  void *left[lsize];		// The left half
  void *right[rsize];		// The right half

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

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

  // Sort the two subarrays
  sort (left, 0, lsize-1, comp);
  sort (right, 0, rsize-1, comp);

  // And join them back together
  merge (subvals, size, left, lsize, right, rsize, comp);
} // sort