← Knowledgebase

Quicksort: partitioning

The idea

Quicksort is divide and conquer. Pick one key as the pivot. Rearrange the array so that every smaller key comes before the pivot and every larger key after it. That step is called partitioning. The pivot is now in its final sorted position. Then sort the left side and the right side the same way. A side with zero or one key is already sorted.

All the real work happens in partitioning, so that is what these pages drill.

Lomuto partitioning

For the range of indices lo…hi:

  1. The pivot is the last key, at hi.
  2. Pointer i marks the end of the "smaller" part; it starts at lo.
  3. Pointer j scans from lo to hi − 1. If the key at j is smaller than the pivot, swap it to index i and move i right. Otherwise, leave it.
  4. Finally, swap the pivot into index i: between the two parts.

At every moment the range looks like this:

low smaller than the pivot (before i) high larger (from i up to j) ? not examined yet pivot the pivot done in its final place

Cost

Quicksort
Average timeO(n log n): pivots usually split ranges roughly in half, so there are about log n levels of partitioning, each touching n keys.
Worst timeO(n²): if the pivot is always the largest or smallest key, each partition peels off just one key. With "last key as pivot", an already sorted array does exactly that. Try it in the walkthrough.
Extra spaceIn place; O(log n) for the recursion on average.
Stable?No.

Real implementations avoid the worst case by choosing the pivot at random or as the median of three keys. Many use Hoare's partitioning, which scans from both ends and swaps less. Compare with heapsort, which guarantees O(n log n) but is usually slower in practice.