Quick Sort

Introduction

Quick sort is a highly efficient divide-and-conquer sorting algorithm developed by Tony Hoare in 1959 and published in 1961. It is widely regarded as the fastest general-purpose sorting algorithm in practice, and it serves as the default sorting algorithm in many programming language standard libraries, including C's qsort and earlier versions of Java's Arrays.sort for primitives.

The algorithm works by selecting a "pivot" element and partitioning the array so that all elements less than the pivot come before it and all elements greater than the pivot come after it. The pivot is then in its final sorted position, and the algorithm recursively sorts the subarrays on either side.

Quick sort's average-case time complexity of O(n log n) is achieved with excellent constant factors, making it faster than merge sort and heap sort in most practical scenarios. However, its worst-case complexity of O(n^2) can occur with poor pivot choices. Modern implementations use techniques such as median-of-three pivot selection and introsort to mitigate this risk.

"Quicksort is the fastest known comparison-based sorting algorithm when applied to large, unordered, random datasets. Although its worst-case running time is quadratic, its average-case running time is O(n log n) with very small constant factors." -- Thomas H. Cormen, Introduction to Algorithms

How It Works

Divide-and-Conquer Strategy

Quick sort partitions the array around a pivot element and then recursively sorts the partitions:

1. Choose a pivot: Select an element from the array to serve as the pivot. Common strategies include choosing the first element, the last element, a random element, or the median of three elements.
2. Partition: Rearrange the array so that all elements less than the pivot are to its left, and all elements greater than the pivot are to its right. The pivot is now in its final sorted position.
3. Recurse: Recursively apply quicksort to the subarray of elements before the pivot and the subarray of elements after the pivot.
4. Base case: Subarrays of zero or one element are already sorted and require no processing.

The Partition Operation

The partition step is the key operation that distinguishes quicksort. The Lomuto partition scheme uses the last element as pivot and maintains an index i such that all elements at positions up to i are less than or equal to the pivot. The Hoare partition scheme uses two pointers that move toward each other and is more efficient in practice, performing about three times fewer swaps on average.

Algorithm and Pseudocode

Main Algorithm

procedure quickSort(A : array, low : int, high : int) if low < high then pivotIndex := partition(A, low, high) quickSort(A, low, pivotIndex - 1) // Sort left partition quickSort(A, pivotIndex + 1, high) // Sort right partition end ifend procedure

Lomuto Partition Scheme

function partition(A : array, low : int, high : int) : int pivot := A[high] // Choose last element as pivot i := low - 1 // Index of smaller element boundary for j := low to high - 1 do if A[j] <= pivot then i := i + 1 swap(A[i], A[j]) end if end for swap(A[i + 1], A[high]) // Place pivot in correct position return i + 1end function

Hoare Partition Scheme

function hoarePartition(A : array, low : int, high : int) : int pivot := A[low] // Choose first element as pivot i := low - 1 j := high + 1 loop do i := i + 1 while A[i] < pivot do j := j - 1 while A[j] > pivot if i >= j then return j swap(A[i], A[j]) end loopend function

The Hoare scheme returns an index such that all elements at or before the index are less than or equal to the pivot, and all elements after the index are greater than or equal to the pivot. The recursive calls are then made on A[low..j] and A[j+1..high].

Time and Space Complexity

Space Complexity: O(log n) average case for the recursion stack. In the worst case, when the partitioning is maximally unbalanced, the recursion depth can reach O(n). Tail-call optimization or iterating on the larger partition and recursing on the smaller one limits the worst-case stack depth to O(log n).

Stability: Quick sort is not stable in its standard form. The partition operation can change the relative order of elements with equal keys. Stable variants exist but require additional memory or more complex partitioning schemes.

Why O(n^2) Worst Case?

If the pivot consistently divides the array into one subarray of size 0 and one of size n - 1, the recurrence becomes T(n) = T(n - 1) + O(n), which resolves to O(n^2). This occurs when the array is already sorted (or reverse sorted) and the first or last element is chosen as the pivot.

Worked Example

Sort the array [6, 3, 8, 2, 7, 4] using quick sort with the Lomuto partition scheme (last element as pivot).

First Partition (pivot = 4)

The pivot 4 is now at index 2. Elements to its left [3, 2] are all less than 4. Elements to its right [6, 7, 8] are all greater than 4.

Subsequent Recursive Calls

• Left subarray [3, 2] with pivot 2: After partitioning, produces [2, 3]. Both are in their final positions.
• Right subarray [6, 7, 8] with pivot 8: After partitioning, produces [6, 7, 8]. Then [6, 7] is sorted with pivot 7, yielding [6, 7].

Final sorted array: [2, 3, 4, 6, 7, 8]

Advantages and Disadvantages

Advantages

• Fastest in practice: Quicksort's excellent cache locality and low constant factors make it the fastest comparison-based sorting algorithm for most real-world data.
• In-place: Requires only O(log n) extra space for the recursion stack, compared to O(n) for merge sort.
• Cache-friendly: Sequential memory access during partitioning leads to excellent cache performance.
• Tail recursion: The second recursive call can be eliminated via tail-call optimization, reducing stack usage.
• Versatile: Many variants exist (randomized, dual-pivot, three-way) that address different performance concerns.

Disadvantages

• O(n^2) worst case: Poor pivot selection can cause quadratic behavior, which is unacceptable for adversarial inputs or real-time systems.
• Not stable: Elements with equal keys may change their relative order.
• Recursive: Deep recursion on large arrays can cause stack overflow without tail-call optimization.
• Sensitive to pivot choice: Performance depends heavily on how the pivot is selected.

Comparison with Other Algorithms

Quick Sort vs. Merge Sort: Quicksort is faster in practice due to better cache performance and no need for auxiliary arrays. However, merge sort guarantees O(n log n) worst-case time and is stable. For applications where worst-case guarantees or stability are required, merge sort is preferred.

Quick Sort vs. Heap Sort: Heap sort guarantees O(n log n) in all cases and uses O(1) extra space, but its poor cache locality makes it 2-5 times slower than quicksort in practice. Introsort combines the two: it starts with quicksort and switches to heap sort if the recursion depth exceeds O(log n), guaranteeing O(n log n) worst-case performance.

Quick Sort vs. Introsort: Introsort is essentially quicksort with a safety net. It monitors recursion depth and switches to heap sort if degradation is detected, eliminating the O(n^2) worst case while preserving quicksort's practical speed. The C++ STL std::sort uses introsort.

Implementation Notes

Pivot Selection Strategies

• First or last element: Simple but vulnerable to O(n^2) on sorted or nearly sorted input.
• Random element: Randomized quicksort selects a random pivot, giving O(n log n) expected time regardless of input distribution.
• Median of three: Choose the median of the first, middle, and last elements. This performs well on most inputs and avoids worst-case behavior on sorted data.
• Ninther (median of medians of three): Used in some high-performance implementations for very large arrays.

Three-Way Partitioning (Dutch National Flag)

When the array contains many duplicate elements, standard quicksort can degrade because equal elements are distributed across both partitions. Three-way partitioning (due to Dijkstra) divides the array into three regions: less than, equal to, and greater than the pivot. This runs in O(n) time when all elements are equal, and O(n log n) on average.

procedure threeWayPartition(A : array, low : int, high : int) pivot := A[low] lt := low // A[low..lt-1] < pivot gt := high // A[gt+1..high] > pivot i := low // A[lt..i-1] == pivot while i <= gt do if A[i] < pivot then swap(A[lt], A[i]) lt := lt + 1 i := i + 1 else if A[i] > pivot then swap(A[i], A[gt]) gt := gt - 1 else i := i + 1 end if end while // Recurse on partitions with elements != pivot quickSort(A, low, lt - 1) quickSort(A, gt + 1, high)end procedure

Dual-Pivot Quick Sort

Java's Arrays.sort for primitive types uses Vladimir Yaroslavskiy's dual-pivot quicksort. It selects two pivots and partitions the array into three parts: elements less than the smaller pivot, elements between the two pivots, and elements greater than the larger pivot. This reduces the number of comparisons and swaps compared to single-pivot quicksort.

Applications

• General-purpose sorting: The default sorting algorithm in many standard libraries (C's qsort, earlier Java Arrays.sort for primitives).
• Database systems: Used for sorting query results when memory is sufficient and worst-case guarantees are not critical.
• Quickselect: A related algorithm based on quicksort's partition step that finds the k-th smallest element in O(n) expected time.
• Introsort: The C++ STL std::sort uses introsort, which is quicksort with fallback to heap sort for guaranteed O(n log n) worst-case performance.
• Parallel sorting: The independent partitions can be sorted in parallel, though the partition step itself is sequential.
• Virtual memory systems: Quicksort's in-place nature and sequential access patterns work well with memory paging systems.

References

• Hoare, C. A. R. "Quicksort." The Computer Journal, 5(1):10-16, 1962.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. Introduction to Algorithms, 4th Edition. MIT Press, 2022. Chapter 7: Quicksort.
• Sedgewick, R. "Implementing Quicksort Programs." Communications of the ACM, 21(10):847-857, 1978.
• Bentley, J. L. and McIlroy, M. D. "Engineering a Sort Function." Software: Practice and Experience, 23(11):1249-1265, 1993.
• Yaroslavskiy, V. "Dual-Pivot Quicksort." Technical report, 2009.