QuickSort can be tricky and atleast one of its implementations printed in a widely used book had in it a subtle bug.

Found an excellent concise implementation in the book “Programming Pearls” by John Bentley.

void quicksort(int left, int right)

{

if ( left <= right ) return;

int pivotIndex = rand(left, right);

int pivotValue = x[pivotIndex];

swap(x[left], x[pivotIndex]);

int partitionIndex = left;

for (int i = left + 1 ; i <= right; i ++)

if ( x[i] < pivotValue ) swap ( x[++partitionIndex], x[i]);

swap (x[left], x[partitionIndex]);

quicksort(left, partitionIndex -1);

quicksort(partitionIndex + 1, right);

}

Lets see how we could build the above program:

Step 1: Need a find a partition point m. Given m, we need to recurse with quicksort(l, m -1); quicksort (m + 1, u);

Step 2: For recursive programs, an exit strategy is required. if ( l >= u) return;

Step 3: It is difficult to have the pivot value in exactly the middle of the array bcz:

1. We really want to select the pivot location randomly.

2. There is no guarantee that the pivot value will end up dividing the array in two equal subarrays.

As John B mentions in the video, humans are prone to symmetry potentially leading to complex code in the quicksort implementations. So the approach to take is : select a pivot randomly and move it to the first location of the array.

And beautiful code is born !