The quicksort algorithm sorts an array by first selecting a pivot entry and partitioning the array about that element. The partition operation rearranges the entries, placing the pivot entry in its proper sort position. After the partition, entries before (in index order) the pivot entry are less than the pivot entry. Entries after the pivot entry are greater than or equal to the pivot entry. This is illustrated in the following diagram, where the index geq points to the pivot entry.

lo geq hi
< = >=

Then the quicksort algorithm recursively sorts the entries before the pivot entry and the entries after the pivot entry.


After checking if there is more than one element (if not then just return), a pivot element is selected and swapped with the end entry. This is done to keep the pivot entry in a known place. It will later be swapped into its proper place.

Two variables geq and unk are set equal to lo, the lowest index in the array segment. This indicates that the "<" and ">=" segments of the array are currently empty.

A variable end is set equal to hi - 1, where hi is the index just beyond the end of the segment. This results in the following picture. The partition loop only works with the portion outlined in blue.

lo end hi
? =

Here ? indicates unknown entries - entries that have not yet been examined.

The Loop Invariant

The two preceding pictures can be generalized into a single picture that covers both.

lo geq unk end hi
< >= ? =

Here, < indicates entries that are less than the pivot and >= indicates entries that are greater than or equal to the pivot.

Since this picture covers both the starting picture, the end result, and intermediate steps, it can be used as a loop invariant.

Each iteration of the loop checks the entry at index unk. If it is less than piv then the entry is swapped with the entry at geq and both geq and unk are advanced. Otherwise unk is advanced. In either case, the loop invariant is preserved.

Loop Termination

When finally unk == end we have the following picture.

lo geq end hi
< >= =

A Final Step

Now the entry at index geq is swapped with the pivot at index end. This results in the following picture.

lo geq hi
< = >=

After achieving this picture, the array can be completely sorted by recursively sorting the < and >= regions.