Python quicksort and partitioning
Partition around a pivot, then sort smaller subproblems.
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]
Explanation
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.
Explore the dry run
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] |
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].