Quicksort & Partitioning
How quicksort picks a pivot, slices the array in a single pass, and recurses — plus why a bad pivot turns O(n log n) into O(n²) and how to avoid it.
What you'll learn
- How Lomuto partition places a pivot in O(n) and why the pivot is then permanently home
- Why quicksort averages O(n log n) but degrades to O(n²) on already-sorted input with a naive pivot
- The three practical pivot strategies — last element, random, median-of-three — and when each matters
- Why quicksort (introsort) is the default in-memory sort in most standard libraries despite the O(n²) worst case
Before you start
Quicksort does something conceptually simple: pick one element as a pivot, reorganize the array so everything smaller is to its left and everything larger is to its right, and then repeat on each side. After the reorganization — called a partition — the pivot is in its final, sorted position forever. You never touch it again.
The intuition
Imagine laying out a hand of playing cards and picking one at random as your pivot. You slide every card smaller than it to the left, every card larger to the right, and drop the pivot in the gap. You now have three groups: left (unsorted, but all smaller), pivot (done), right (unsorted, but all larger). Run the same procedure on the left group, then the right group, and so on. The deck sorts itself through a sequence of partitions.
The key insight: one partition takes O(n) time and permanently fixes one element. If the pivot always lands near the middle, each level of recursion halves the problem — n log n total work.
The partition step
The most common implementation is Lomuto partition. It maintains two pointers:
i— the “store” index; everything to its left is already less than the pivot.j— the “scan” index; it walks forward comparing each element to the pivot.
When arr[j] is smaller than the pivot, it gets swapped into position i, and i advances. After the scan, the pivot is swapped from its holding position at the end into index i.
Use Step to walk through one comparison at a time. Notice how the store pointer lo (shown in purple) advances only when a swap happens, while the scan pointer hi (shown in teal) moves every step. Switch to sorted input with last pivot to see the worst case: the pivot always lands at the edge, so every level does O(n) work — n levels, n² total.
Code
Complexity
| Case | Time | Space |
|---|---|---|
| Average | O(n log n) | O(log n) stack |
| Best | O(n log n) | O(log n) stack |
| Worst | O(n²) | O(n) stack |
In-place: the partition happens inside the original array — no auxiliary array needed. Stack depth is O(log n) on average (O(n) worst case with a bad pivot sequence).
Not stable: equal elements can change relative order during swaps (recall: a sort is stable if equal elements keep their original relative order).
Average O(n log n): a pivot does not need to land exactly at the median — it just needs to avoid the extremes. Any pivot that falls in the middle half of the values (25th–75th percentile) produces a constant-fraction split, and that happens with probability 1/2 on each random choice. The expected recursion depth is O(log n) and the expected comparisons per level sum to O(n), giving O(n log n) overall.
Why quicksort dominates in practice
Merge sort also achieves O(n log n) worst case, but it requires O(n) extra memory for the merge step. Quicksort is in-place, which means better cache locality — the elements being compared sit close together in memory. This constant-factor advantage is large enough that quicksort (as introsort) beats merge sort on random data in most benchmarks.
Standard library connections:
- C++
std::sort— introsort (quicksort + heapsort fallback + insertion sort for small sub-arrays). - Python
list.sort()/sorted()— Timsort (merge sort variant), butnumpy.sort(kind="quicksort")invokes an introsort variant. - Java
Arrays.sortfor primitives — dual-pivot quicksort (Yaroslavskiy). - Rust
slice::sort_unstable— pattern-defeating quicksort (pdqsort).
The theme: pure quicksort is fast but brittle; production sorts wrap it in safeguards that guarantee O(n log n) while keeping the average-case speed.
Quick check
Quick check
Practice this in an interview
All questionsEven after rotation, one of the two halves around mid is always fully sorted. Check which half is sorted, then decide whether the target falls inside it. If yes, narrow to that half; if no, search the other. This keeps binary search's O(log n) guarantee.
Use a slow pointer that tracks where the next unique value should be written, and a fast pointer that scans forward. Whenever the fast pointer finds a value different from the current unique one, copy it to the slow pointer's position and advance both. One pass, O(1) extra space.
Partitioning divides a large table into smaller physical segments (partitions) based on a column value, so the planner can skip irrelevant partitions entirely — a technique called partition pruning. It improves performance for queries that filter on the partition key, and it simplifies bulk data management tasks like dropping old data by dropping a partition instead of issuing a slow DELETE.
Binary search halves the search space each iteration to find a target in O(log n). The tricky part is not the idea but the boundary conditions: closed vs. half-open intervals, how to update lo/hi, and when to use lo < hi vs. lo <= hi. One clean template eliminates all the classic bugs.