/**
 * qsort.c -
 *   K&R's Quicksort routine, updated slightly.
 */

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

#include "sort.h"	// Make sure we match the signature
#include "swap.h"	// For swap


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

/**
 * sort: sort v[left]...v[right] into increasing order using
 *   comp to compare strings.
 *   Note: Renamed to avoid conflict with qsort in stlib.h.
 */ 
void 
sort (void *v[], 
      int left, int right, 
      int (*comp)(const void *s1, const void *s2))
{
  int i, last;

  /* If the array contains fewer than two elements, do nothing. */
  if (left >= right) 
    return;
  swap(v, left, (left + right)/2);
  last = left; 
  for (i = left+1; i <= right; i++) 
    if ((*comp)(v[i], v[left]) < 0)
      swap(v, ++last, i); swap(v, left, last);
   sort (v, left, last-1, comp); 
   sort (v, last+1, right, comp);
} // sort