quicksort
=========

/* Quicksort: Pointer version with macros. */

#define swap(x, y)	{int t; t = x; x = y; y = t;}
#define order(x,y)	if (x > y) swap(x, y)
#define o2(x, y)	order(x, y)
#define o3(x, y, z)	o2(x, y); o2(x, z); o2(y, z)
#define N		12

typedef enum {yes, no}	yes_no;

static  yes_no	find_pivot(int *left, int *right, int *pivot_ptr);
static  int   	*partition(int *left, int *right, int pivot);

main()
{
  int i, a[N] = {7, 4, 3, 5, 2, 5, 8, 2, 1, 9, -6, -3};
  void quicksort(int*, int*);
  
  quicksort(a, a + N - 1);
  for (i = 0; i < N; ++i)
    printf("%d   ", a[i]);
  printf("\n");
}

void quicksort(int *left, int *right)
{
   int *p, pivot;

   if (find_pivot(left, right, &pivot) == yes) {
      p = partition(left, right, pivot);
      quicksort(left, p - 1);
      quicksort(p, right);
   }
}



static yes_no find_pivot(int *left, int *right, int *pivot_ptr)
{
   int a, b, c, *p;

   a = *left;				/* left value */
   b = *(left + (right - left) / 2);	/* middle value */
   c = *right;				/* right value */
   o3(a, b, c);  /* order these 3 values */
   if (a < b) {  /* pivot will be higher of these two values */
      *pivot_ptr = c;
      return yes;
   }
   for (p = left + 1; p <= right; ++p)
      if (*p != *left) {
	 *pivot_ptr = (*p < *left) ? *left : *p;
	 return yes;
      }
   return no;    /* all elements have the same value */
}

static int *partition(int *left, int *right, int pivot)
{
   while (left <= right) {
      while (*left < pivot)
	 ++left;
      while (*right >= pivot)
	 --right;
      if (left < right) {
	swap(*left, *right);
	++left;
	--right;
      }
   }
   return left;
}

Output
=======

-6   -3   1   2   2   3   4   5   5   7   8   9