Quick Sort
A medium Sorting interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Sorting
- Sheets
- 3
- Core for
- 13 roles
The problem
Sort an array by selecting a pivot element, partitioning the other elements into those less than and greater than the pivot, and recursively sorting the partitions.
Example 1
- Input
- nums = [10, 7, 8, 9, 1, 5]
- Output
- [1, 5, 7, 8, 9, 10]
Example 2
- Input
- nums = [5, 1, 1, 2, 0, 0]
- Output
- [0, 0, 1, 1, 2, 5]
Constraints
- 1 <= nums.length <= 5 * 10^4
- -10^5 <= nums[i] <= 10^5
How to think about it
Updated 2026-09-29Unlike merge sort which does all its combination work on the way back up, quicksort does its hard work on the way down. Choosing a pivot and segregating values around it locks that pivot into its exact final index immediately, splitting the rest into two completely independent subproblems that require no merging afterward.
Approaches, worst first
Naive fixed pivot Lomuto
time O(n^2) · space O(n)
Pick the last element as pivot and advance a single slow pointer swapping items smaller than pivot forward. Very concise, but degenerates to quadratic runtime and deep call stacks on already sorted arrays or arrays with repeated values.
Hoare partition with random pivot
time O(n log n) · space O(log n)
Swap a randomized or median-of-three element into the pivot position, then march pointers from both ends inward until they find out-of-place pairs to swap. Performs three times fewer swaps on average than Lomuto and handles duplicates cleanly.
Three-way Dutch flag partitionWrite this one
time O(n log n) · space O(log n)
Partition the array into three regions: strictly less than, equal to, and strictly greater than the pivot. Avoids recursive calls on identical elements, preventing quadratic degradation on arrays filled with duplicate keys.
Where people lose marks · 3
- Always picking the first or last element as pivot: an already sorted or reverse-sorted input triggers the worst-case O(n^2) time and exhausts the call stack.
- Infinite loops in two-pointer partitioning when both pointers halt on elements equal to the pivot; pointers must cross or increment after a swap to guarantee progress.
- Failing to recurse on the smaller partition first in languages with limited stack space, which risks stack overflow when partitions become unbalanced.
The theory behind it
Sorting — the ground this problem stands on. All Sorting problems
What Sorting is
Sorting is the act of arranging a scrambled hand of playing cards into ascending rank from left to right. It reorganizes scattered data according to a consistent comparison rule, like numbering index cards or alphabetizing names. While unsorted data requires searching every single entry to verify whether an item exists, ordered data establishes predictable relationships that make duplicates, clusters, and extreme values immediately visible.
When to reach for it
Reach for sorting when a problem asks to group identical items, detect overlaps among intervals, find rank percentiles, or pair values matching a target sum. If an unordered problem appears intractable in polynomial time, sorting the input frequently unlocks linear scans or two-pointer sweeps. When an O(n log n) preprocessing step simplifies downstream matching logic, sorting is usually the right opening move.
How the pattern works
Think of sorting as a trade: invest logarithmic overhead upfront to make subsequent queries direct and orderly. Compare adjacent elements to uncover duplicate entries, or march inward from outer boundaries once elements stand in monotonic sequence. When designing custom comparators, confirm strict weak ordering by verifying reflexivity, antisymmetry, and transitivity; inconsistent comparison logic breaks internal pivot partitions or produces corrupted outputs.
More Sorting problems
Target Roles
Core requirement for 13 roles:
Asked at
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .