Python quicksort and partitioning
Partition around a pivot, then sort smaller subproblems.
On this page
Recursion, comparisons, and comprehensions.
- Partition around a pivot, then sort smaller subproblems.
- Predict the sample output and explain the state changes.
- Complete the practice task and check the boundary cases.
The concept
Quicksort partitions values into those below, equal to, and above a pivot. Only the below and above groups need recursive sorting.
This readable version allocates lists rather than partitioning in place. A middle-position pivot is deterministic but does not guarantee balanced partitions for every input.
Code example
def quick_sort(values):
if len(values) <= 1:
return values.copy()
pivot = values[len(values) // 2]
lower = [value for value in values if value < pivot]
equal = [value for value in values if value == pivot]
upper = [value for value in values if value > pivot]
return quick_sort(lower) + equal + quick_sort(upper)
print(quick_sort([3, 1, 2, 1]))
assert quick_sort([]) == []
assert quick_sort([2, 2]) == [2, 2][1, 1, 2, 3]
Follow the code
Open the walkthrough to inspect the example one step at a time.
Show guided walkthrough
def quick_sort(values): if len(values) <= 1: return values.copy() pivot = values[len(values) // 2] lower = [value for value in values if value < pivot] equal = [value for value in values if value == pivot] upper = [value for value in values if value > pivot] return quick_sort(lower) + equal + quick_sort(upper) print(quick_sort([3, 1, 2, 1]))assert quick_sort([]) == []assert quick_sort([2, 2]) == [2, 2]Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| The top-level middle position holds 2. | pivot = 2 | — | |
| Collect values below 2. | lower = [1, 1] | — | |
| Keep all equal values. | equal = [2] | — | |
| Collect values above 2. | upper = [3] | — | |
| Sort [1,1] into one equal group and use the [3] base case; concatenate. | return = [1, 1, 2, 3] | — | |
| Print the result. | return = [1, 1, 2, 3] | [1, 1, 2, 3] |
Behind the scenes
How Python processes this code
Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.
Cost and common mistakes
O(n log n) time for balanced partitions, O(n²) worst-case. This allocating implementation can retain O(n²) space across a worst-case recursion chain; it is not in-place.
- Dropping the equal group loses duplicates.
- Inputs must have a consistent total ordering; NaN values do not satisfy ordinary comparison assumptions.
Try it yourself
Predict the partition groups for [4, 2, 4].
Reveal answer and reasoning
The pivot is 2: lower=[], equal=[2], upper=[4,4], producing [2,4,4].