Quick Sort

Introduction

Quick sort, developed by Tony Hoare in 1959 and published in 1961, is one of the most widely used sorting algorithms in practice. Despite its O(n^2) worst-case time complexity, its average-case O(n log n) performance with small constant factors, in-place operation, and cache efficiency make it the algorithm of choice for most general-purpose sorting tasks.

Quick sort exemplifies the divide and conquer paradigm, but with an important twist: unlike merge sort where the work happens in the combine step, in quick sort all the work happens in the divide step (partitioning). Once the array is partitioned around a pivot, the subarrays can be sorted independently with no merge step needed.

Quick Sort as Divide and Conquer

1. Divide: Choose a pivot element and partition the array so that all elements less than the pivot come before it, and all elements greater come after it. The pivot is now in its final sorted position.
2. Conquer: Recursively sort the subarray of elements before the pivot and the subarray of elements after the pivot.
3. Combine: Nothing to do -- the array is already sorted because the partition placed the pivot correctly and the recursive calls sorted the subarrays in place.

Pseudocode

procedure QuickSort(arr, low, high): if low < high: pivotIndex = Partition(arr, low, high) QuickSort(arr, low, pivotIndex - 1) QuickSort(arr, pivotIndex + 1, high)

Quick sort's elegance lies in the partition step: a single linear scan places one element in its correct final position and divides the problem into two independent subproblems. No additional memory is needed for combining results.

Partition Schemes

Lomuto Partition

Uses the last element as the pivot. Maintains a boundary index i such that all elements from low to i are less than or equal to the pivot.

procedure LomutoPartition(arr, low, high): pivot = arr[high] i = low - 1 for j from low to high - 1: if arr[j] <= pivot: i = i + 1 swap(arr[i], arr[j]) swap(arr[i + 1], arr[high]) return i + 1

Hoare Partition

Uses two pointers that move toward each other, swapping elements that are on the wrong side of the pivot. Generally performs fewer swaps than Lomuto.

procedure HoarePartition(arr, low, high): pivot = arr[low] i = low - 1 j = high + 1 loop: do: i = i + 1 while arr[i] < pivot do: j = j - 1 while arr[j] > pivot if i >= j: return j swap(arr[i], arr[j])

Pivot Selection Strategies

First or Last Element

Simplest approach, but degrades to O(n^2) on already-sorted or reverse-sorted input.

Random Element

Randomly select the pivot. This makes worst-case behavior extremely unlikely regardless of input order. Expected time is O(n log n).

Median of Three

Choose the median of the first, middle, and last elements. This is a good compromise that avoids worst-case behavior on sorted input and is used in many practical implementations.

Median of Medians

A deterministic O(n) algorithm that finds the true median, guaranteeing O(n log n) worst case. However, the large constant factor makes it impractical; it is primarily of theoretical interest (Blum, Floyd, Pratt, Rivest, and Tarjan, 1973).

Worked Example

Sort [10, 80, 30, 90, 40, 50, 70] using Lomuto partition (last element as pivot):

Step 1: pivot = 70. Partition: [10, 30, 40, 50, 70, 90, 80]. Pivot at index 4.

Step 2: Left subarray [10, 30, 40, 50]. pivot = 50. Partition: [10, 30, 40, 50]. Pivot at index 3.

Step 3: Left subarray [10, 30, 40]. pivot = 40. Partition: [10, 30, 40]. Pivot at index 2.

Step 4: Left subarray [10, 30]. pivot = 30. Partition: [10, 30]. Pivot at index 1.

Step 5: Right subarray of step 1: [90, 80]. pivot = 80. Partition: [80, 90]. Pivot at index 5.

Result: [10, 30, 40, 50, 70, 80, 90].

Complexity Analysis

Space complexity: O(log n) average for the recursion stack with good pivots. O(n) in the worst case with degenerate pivots. Tail-call optimization on the larger subarray (always recurse on the smaller half) guarantees O(log n) stack depth.

Recurrence Relations

Best case: T(n) = 2T(n/2) + O(n). By the Master theorem: T(n) = O(n log n).

Worst case: T(n) = T(n-1) + O(n). This telescopes to T(n) = O(n^2).

Average case: T(n) = (1/n) * sum over k=0 to n-1 of [T(k) + T(n-1-k)] + O(n). The solution is T(n) = O(n log n) with a constant of approximately 1.39 * n * ln(n), which is about 39% more comparisons than the best case.

Even a very unbalanced partition, say 9:1, still gives O(n log n) time. The worst case only occurs with extreme imbalance (0:n-1) at every level, which random pivot selection makes vanishingly unlikely.

Optimizations

• Three-Way Partition (Dutch National Flag): Handles duplicate keys efficiently by partitioning into three groups: less than, equal to, and greater than the pivot. This gives O(n) performance on arrays with many duplicates.
• Insertion Sort for Small Subarrays: When the subarray size falls below a threshold (typically 10-20), switch to insertion sort, which has lower overhead for small inputs.
• Tail Recursion Elimination: Eliminate the recursive call on the larger partition by using a loop, reducing stack depth to O(log n).
• Introsort: Start with quick sort but switch to heap sort if the recursion depth exceeds 2*log2(n). This guarantees O(n log n) worst case while maintaining quick sort's average-case performance. Used by C++ STL's std::sort.

Quick Sort vs Merge Sort

References

• Hoare, C. A. R. "Quicksort." The Computer Journal, vol. 5, no. 1, 1962, pp. 10-16.
• Sedgewick, R. "Implementing Quicksort Programs." Communications of the ACM, vol. 21, no. 10, 1978, pp. 847-857.
• Bentley, J. L. and McIlroy, M. D. "Engineering a Sort Function." Software: Practice and Experience, vol. 23, no. 11, 1993, pp. 1249-1265.
• Blum, M., Floyd, R. W., Pratt, V., Rivest, R. L., and Tarjan, R. E. "Time Bounds for Selection." Journal of Computer and System Sciences, vol. 7, 1973, pp. 448-461.
• Musser, D. R. "Introspective Sorting and Selection Algorithms." Software: Practice and Experience, vol. 27, no. 8, 1997, pp. 983-993.