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.

#### Initialization

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.

 unk geq 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.

 unk 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.