// a structured quick sort algorithm written in pure C
// this is an adaptation of an adaptation of Tony Hoare's original algorithm
// credits to my teacher for the original structured adaptation
// I changed his function to make it work with arbitrary pointers, not just
// an array and 2 indexes.
// There is quite a bit of repeated code,
// but it's a decent price to pay for otherwise clean, structured code.
//
// begin has to be before end in memory.
void qsort( int *begin, int *end ) {
  int *b = begin, *e = end, aux,
   pivot = begin[ (begin - end) / 2 ]; // the pivot is the middle of the array

  // search for the first element that's greater than or equal to the pivot
  while ( *b < pivot )
    b++;

  // search for the first element that's less than or equal to the pivot
  while ( *e > pivot )
    e--;

  while ( b < e ) { // if the pointers haven't crossed
    aux = *b; // swap the values
    *b = *e;
    *e = aux;

    // search for the first element that's greater than or equal to the pivot
    do
      b++;
    while ( *b < pivot );

    // search for the first element that's less than or equal to the pivot
    do
      e--;
    while ( *e > pivot );
  }

  // now [ begin..e ] are less than or equal to the pivot... 
  if ( begin < e )
    qsort( begin, e );

  // ...and [ e + 1..end ] are greate than or equal to it
  if ( e + 1 < end )
    qsort( e + 1, end );
}