Quick Sort

Quick Sort is a highly efficient divide-and-conquer sorting algorithm developed by Tony Hoare in 1959 while he was a visiting student at Moscow State University. He was working on a machine translation project and needed to sort words in Russian sentences to look them up in a dictionary. His elegant solution became one of the most important and widely used algorithms in the history of computer science.

Historical Context

Hoare conceived Quick Sort in 1959 and published it in 1961. The algorithm was remarkable for its simplicity and speed. In the decades since, Quick Sort and its variants have become the default sorting algorithm in many programming language standard libraries. C's qsort function, C++'s std::sort (via Introsort), and Java's Arrays.sort for primitive types all use Quick Sort or Quick Sort-based hybrids. Hoare received the Turing Award in 1980 for his contributions to programming language design and methodology, and Quick Sort remains one of his most celebrated inventions.

How It Works

1. Choose pivot: Select an element from the array as the pivot. Common strategies include choosing the first element, the last element, a random element, or the median-of-three (the median of the first, middle, and last elements).
2. Partition: Rearrange the array so that all elements smaller than the pivot are on the left, and all elements larger are on the right. The pivot is placed in its final sorted position. Hoare's original partition scheme uses two pointers that converge from opposite ends, while the Lomuto partition scheme uses a single scan pointer and is simpler to implement but slightly less efficient.
3. Recurse: Recursively apply Quick Sort to the sub-array of elements before the pivot and the sub-array after the pivot.
4. Base case: Arrays of zero or one element are already sorted and require no work.

The partition step is the heart of the algorithm. After partitioning, the pivot element is guaranteed to be in its final position, and the two sub-arrays can be sorted independently.

Complexity

The worst case occurs when the pivot is always the smallest or largest element, producing maximally unbalanced partitions. This happens with already-sorted input when using the first or last element as pivot. Randomized pivot selection makes this event astronomically unlikely, and the median-of-three strategy further reduces the probability. The O(log n) space comes from recursion stack depth in the balanced case; in the worst case, the recursion depth reaches O(n).

Why Quick Sort Is Fast in Practice

Despite having a worse worst-case bound than Merge Sort and Heap Sort, Quick Sort is typically the fastest comparison sort in practice for several reasons. First, it sorts in-place, avoiding the memory allocation overhead of Merge Sort. Second, it has excellent cache locality -- the partition step scans through contiguous memory, which modern CPUs handle very efficiently with their cache hierarchies. Third, the inner loop of the partition step is extremely simple, involving only a comparison, a pointer increment, and occasionally a swap. These factors combine to give Quick Sort a small constant factor in its running time.

Pivot Selection Strategies

The choice of pivot profoundly affects Quick Sort's performance. Fixed pivot selection (always first or last element) leads to O(n^2) on sorted or reverse-sorted input. Random pivot selection gives O(n log n) expected time regardless of input. Median-of-three selects the median of the first, middle, and last elements, providing a good pivot with minimal overhead. Ninther (median of medians of three) is used in some high-performance implementations for even better pivot quality.

When to Use

Quick Sort is the default choice for general-purpose in-memory sorting when average-case performance is the priority. Its in-place operation and cache-friendly behavior make it faster than Merge Sort for arrays in practice. For guaranteed worst-case performance, use Introsort, which combines Quick Sort with Heap Sort as a fallback. When stability is required, Merge Sort or Timsort should be used instead, as Quick Sort is not stable in its standard form.