Back to Study Material Data Structures and Algorithms

Quick Sort

Quick sort is widely regarded as the fastest general-purpose sorting algorithm in practice despite having an O(n squared) worst-case time complexity. It wo...

Quick Sort

Partitioning Around a Pivot

Quick sort is widely regarded as the fastest general-purpose sorting algorithm in practice despite having an O(n squared) worst-case time complexity. It 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 come after it. The pivot is then in its final sorted position. Quick sort recursively applies the same process to the two subarrays on either side of the pivot.

The partition operation is the critical step. The Lomuto partition scheme picks the last element as the pivot, maintains a boundary index i starting before the array, and scans with index j from left to right. Whenever the element at j is less than or equal to the pivot, increment i and swap array at i with array at j. After the scan, swap array at i plus 1 with the pivot. The pivot is now at index i plus 1, with smaller elements to its left and larger elements to its right.

A worked example: array 10, 7, 8, 9, 1, 5 with pivot 5. After partitioning: 1, 5, 8, 9, 7, 10 where 5 is at index 1. Wait, let us trace carefully. Pivot is 5 (last element). Scan: 10 is not less than or equal to 5, skip. 7, skip. 8, skip. 9, skip. 1 is less than or equal to 5, increment i to 0, swap 1 and 10: 1, 7, 8, 9, 10, 5. End scan. Swap index i+1=1 with pivot: 1, 5, 8, 9, 10, 7. Now 5 is at index 1. Recurse on 1 and 8, 9, 10, 7.

Time complexity: best case O(n log n) when the pivot always splits the array exactly in half. Average case O(n log n) for random data. Worst case O(n squared) when the pivot is always the minimum or maximum, producing maximally unbalanced partitions. Space complexity: O(log n) average for the recursive call stack, O(n) worst case.

Interview tip: always mention randomization when discussing quick sort. Randomly selecting the pivot before each partition eliminates the worst case for any fixed input, reducing the probability of O(n squared) behavior to negligibly small.

Pivot Selection and Worst-Case Avoidance

The choice of pivot is the single most important factor in quick sort's performance. A poor pivot choice leads to unbalanced partitions and O(n squared) behavior. Three pivot selection strategies are worth knowing in detail.

The first strategy is always picking the first or last element. This is simple to implement but catastrophically slow on already-sorted or reverse-sorted input, which is extremely common in practice. On sorted input of n elements, each partition produces one subarray of n minus 1 elements and one empty subarray, leading to n levels of recursion and O(n squared) total time.

The second strategy is random pivot selection. Before each partition, swap a randomly chosen element into the last position and use it as the pivot. Since the pivot is random, no fixed input can reliably trigger the worst case. The expected time complexity is O(n log n) for all inputs.

The third strategy is the median-of-three: compute the median of the first, middle, and last elements and use that as the pivot. This eliminates the worst case for sorted and reverse-sorted inputs while adding only a constant overhead per partition.

The most robust strategy, used in some standard library implementations, is the median-of-medians algorithm, which guarantees an O(n) worst-case pivot selection but has a large constant factor. It is rarely used in practice because randomization is simpler and sufficient.

A worked example: the array 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 sorted ascending. With last-element pivot selection, quick sort degenerates to 45 comparisons. With random pivot, the expected comparisons drop to approximately 28 for this size. With median-of-three on this sorted input, the median of 1, 5, 10 is 5, placing the pivot in the middle and producing a balanced partition.

Time complexity: O(n log n) average and expected with randomization, O(n squared) worst case without it. Space complexity: O(log n) average stack depth.

Interview tip: state that in production implementations you would always use either randomized pivot or introsort (quick sort that switches to heap sort after the recursion depth exceeds 2 log n) to guarantee O(n log n) worst-case behavior.

Three-Way Partitioning and Introsort

Standard two-way partitioning divides the array into elements less than the pivot and elements greater than the pivot. When many elements equal the pivot, this creates imbalanced partitions because all equal elements end up on one side. Three-way partitioning, also called the Dutch National Flag partition, divides the array into three groups: elements less than the pivot, elements equal to the pivot, and elements greater than the pivot. All equal elements are placed in their final positions in a single partition step.

The algorithm uses three pointers: lt, gt, and i. Initially lt equals 0, gt equals n minus 1, and i equals 0. While i is less than or equal to gt, if array at i is less than pivot, swap array at lt with array at i, increment both lt and i. If array at i is greater than pivot, swap array at i with array at gt, decrement gt (do not increment i because the swapped element needs to be examined). If array at i equals pivot, just increment i.

After partitioning, elements at indices lt through gt are all equal to the pivot and are permanently in their correct positions. Recurse only on indices 0 through lt minus 1 and gt plus 1 through n minus 1.

For arrays with many repeated elements, three-way quick sort degrades from O(n log n) to O(n) on arrays where all elements are equal, compared to O(n squared) for two-way quick sort. This makes it the sort of choice for data with low cardinality.

Introsort combines quick sort, heap sort, and insertion sort into a hybrid that guarantees O(n log n) worst-case performance. It begins with randomized quick sort. If the recursion depth exceeds 2 times log n, it switches to heap sort for the remaining subarray. For subarrays of length below 16, it uses insertion sort. This is the algorithm underlying C++ std::sort.

Time complexity: O(n log n) average for quick sort, O(n log n) guaranteed for introsort. Space complexity: O(log n).

Interview tip: when asked about the best sorting algorithm, say introsort for general-purpose in-memory sorting. It combines the average-case speed of quick sort, the worst-case guarantee of heap sort, and the low overhead of insertion sort for small inputs.