C++ : Exploring Sorting part III

I promised to talk about faster sorting algorithms and one of the fastest is the appropriately named quicksort. The algorithm was devised by British computer scientist in 1962! (I told you sorting was an age-old problem). His name is Charles Antony Richard Hoare his original paper is entitled C. A. R. Hoare. "Quicksort," Computer Journal, 1962, 5, p.p. 10-15. and is apparently still the most cited paper on the subject.

Anyway, I read an interesting article on searching (of which sorting is part of the solution) by Alexandrescu and the subject of this and the next blog is basically the good old "exercise for the reader" which I've done. I'm not going to claim that mine is the best or fastest implementation. In fact it performs alot slower the std::sort but there's always room for improvement and it's a good learning exercise. I have yet to completely finish tinkering with it so any suggestions would be welcome. I'd like to remove all recursion and make as many other speed improvements as possible. I also need to write a better testing framework with some proper profiling of the function. But anyway... here's the original quicksort algorithm expressed as a simple, non-generic function in C taken from Michael Lamont whose knowledge base pages have lots of nicely expressed C implementations of sorting algorithms with explanations and metrics

void quickSort(int numbers[], int array_size)
{
  q_sort(numbers, 0, array_size - 1);
}


void q_sort(int numbers[], int left, int right)
{
  int pivot, l_hold, r_hold;

  l_hold = left;
  r_hold = right;
  pivot = numbers[left];
  while (left < right)
  {
    while ((numbers[right] >= pivot) && (left < right))
      right--;
    if (left != right)
    {
      numbers[left] = numbers[right];
      left++;
    }
    while ((numbers[left] <= pivot) && (left < right))
      left++;
    if (left != right)
    {
      numbers[right] = numbers[left];
      right--;
    }
  }
  numbers[left] = pivot;
  pivot = left;
  left = l_hold;
  right = r_hold;
  if (left < pivot)
    q_sort(numbers, left, pivot-1);
  if (right > pivot)
    q_sort(numbers, pivot+1, right);
}

In part III we'll take this, make it generic as we did with the bubbleSort in Part II and use the ideas put forward by Alexandrescu to improve it's speed even further.