Quicksort & partition
Overview
An efficient, in-place, divide-and-conquer sorting algorithm that partitions an array around a pivot.
It is usually the fastest sorting algorithm in practice for in-memory arrays because of excellent cache locality and zero extra space allocation (ignoring the call stack).
Where used: Default sorting algorithm in many language standard libraries (like C's qsort, C++'s std::sort, though often hybridized), Systems where memory allocation is expensive
Why it exists
Problem: Merge Sort is O(n log n) and consistent, but it requires O(n) extra memory to merge the arrays. We want an O(n log n) sort that works entirely in-place.
Naive approach: Use an in-place O(n^2) sort like Insertion or Selection sort.
Better idea: Pick an element (the pivot). Move everything smaller than the pivot to its left, and everything larger to its right. The pivot is now in its final sorted position. Recursively do this for the left and right halves.
Why learn this
- The partition subroutine is a heavily tested interview pattern on its own.
- It teaches you how to think about in-place array manipulation.
- It introduces worst-case vs expected time complexity.
Mental model
Pick a leader (pivot), put all the smaller elements on the left, larger on the right. Now the leader is exactly where it belongs. Repeat for the two groups.
Quicksort revolves around the Partition operation. We maintain a boundary of 'elements smaller than pivot'. As we scan, if we find a small element, we swap it into the small boundary. Once partitioned, we recurse on the left and right partitions.
Repeated decision: Is the current element smaller than the pivot? If yes, swap it into the 'small' section.
Deep dive
Quicksort is a divide-and-conquer algorithm like Merge Sort, but it does all the hard work *before* the recursive calls rather than after. The core of Quicksort is the **Partition** step.
To partition an array, we first pick a `pivot` (often the last element). We use two pointers: one pointer (`i`) keeps track of the boundary of elements smaller than the pivot, and the other pointer (`j`) scans the array. Whenever `j` finds an element smaller than the pivot, we swap it with the element at `i`, and increment `i`. At the end, we swap the pivot itself into position `i`. The pivot is now exactly where it belongs in the final sorted array.
Because the pivot is in its final place, we can recursively call Quicksort on the elements to its left and the elements to its right. If the pivot happens to perfectly divide the array in half each time, the depth of the recursion tree is `O(log n)`. At each level, we do `O(n)` work to partition. This gives an expected time complexity of `O(n log n)`.
However, if the array is already sorted and we always pick the last element as the pivot, the left partition will have `n - 1` elements and the right will have `0`. The recursion tree becomes a straight line of depth `n`, resulting in a worst-case time complexity of `O(n^2)`. This is why modern Quicksort implementations pick a random pivot or the median of three.
Key points
- Complexity: Expected Time is O(n log n). Worst-case Time is O(n^2). Space is O(log n) for the recursion call stack (or O(n) worst case).
- In-place but Unstable: Quicksort uses no extra array allocations, but the swapping during partition destroys the relative order of equal elements, making it an unstable sort.
Pattern: Partitioning
Recognition cues:
- Segregate elements based on a condition
- Sort an array in-place without extra memory
Failure signals
- The data is extremely large and does not fit in memory (external sorting needs Merge Sort).
- You absolutely cannot afford an O(n^2) worst-case delay.
Engineering examples
Language Standard Libraries
Providing a fast generic sorting function.
Languages like C++ use Introsort (a hybrid of Quicksort and Heapsort). It runs Quicksort for speed but falls back to Heapsort if the recursion goes too deep, guaranteeing O(n log n) worst-case.
When not to use
- When stability is required: Quicksort swaps elements across distances, so equal elements might switch relative order. Merge Sort is preferred when stability is needed.
Common mistakes
- Infinite recursion: If the partition function includes the pivot in one of the recursive calls, it can lead to infinite recursion. The recursive calls must strictly be `[start, pivot_index - 1]` and `[pivot_index + 1, end]`.
- Choosing a bad pivot: Always picking the first or last element as the pivot causes O(n^2) behavior on already sorted arrays (a common edge case in real systems).
Recall questions
- What is the expected and worst-case time complexity of Quicksort?
- Why is Quicksort generally faster than Merge Sort in practice despite the same average time complexity?
- How can you prevent the O(n^2) worst-case scenario in Quicksort?
Understanding checks
In the partition step, after we finish scanning and swap the pivot into its final place, what guarantee do we have about the elements to its left and right?
All elements to the left are less than or equal to the pivot, and all elements to the right are greater than the pivot.
This is the core invariant of the partition step. It ensures the pivot is in its globally correct sorted position.
A student wrote a recursive Quicksort call like this: `quicksort(arr, low, p)` and `quicksort(arr, p, high)`. What is wrong?
It will infinitely recurse. The pivot `p` is already in its final position, so the calls should be `quicksort(arr, low, p - 1)` and `quicksort(arr, p + 1, high)`.
Including the pivot in the subarrays means the subarray size might not shrink, leading to a stack overflow.
Questions & answers
Sort Colors (Dutch National Flag)
This is a 3-way partition variation of Quicksort's partitioning step.
Approach: Maintain three pointers: one for the end of 0s, one for the start of 2s, and a current scanner.
Move Zeroes to End
Use the exact same logic as Quicksort's partition. Treat '0' as the pivot value, and swap non-zero elements to the front.
Approach: Maintain a pointer for the boundary of non-zero elements and swap as you iterate.
Practice tasks
Sort an Array
Implement a sorting algorithm to sort the array `nums` in O(n log n) time. Try implementing Quicksort with a random pivot.
Continue learning
Previous: Two pointers
Previous: Recursive tree thinking
Next: Quickselect