Know this before you start: “Partitioning around a pivot (quick sort)”
Partitioning around a pivot
Pick a value, the pivot, and rearrange so everything smaller comes before it and everything larger after. does that, then sorts each side the same way.
The idea
After one partition the pivot is in its final sorted position: nothing on its left is bigger, nothing on its right is smaller. Only the two sides still need sorting.
, a partition is one pass with : keep a boundary for the “smaller” zone and swap each small item into it. Sort Colors (three groups: 0s, 1s, 2s) is the same move.
Quick sort averages with a random pivot. A bad pivot every time (the smallest, on sorted input) makes it . Partitioning alone also finds the k-th smallest in on average.
Worked example
Partition [5, 2, 4, 1, 3] around its last item, 3
- boundary = 0. 5 isn't < 3, skip. 2 is: swap it to the boundary → [2, 5, 4, 1, 3], boundary 1.
- 4 isn't < 3, skip. 1 is: swap it to the boundary → [2, 1, 4, 5, 3], boundary 2.
- Swap the pivot into the boundary → [2, 1, 3, 5, 4]. 3 is at index 2, exactly where it sits when sorted; sort [2, 1] and [5, 4] the same way.
Pseudocode
The steps in plain words. ← means “set to”; indentation shows what's inside what.
See it run
The worked example, step by step, beside the Python. The highlighted line is the one running.
Step-by-step
nums = [5, 2, 4, 1, 3]
Solution · Pythonline 3
def partition(nums, lo, hi):"""Lomuto: nums[hi] is the pivot; returns where it ends up."""pivot = nums[hi]boundary = lo # everything before it is < pivotfor i in range(lo, hi):if nums[i] < pivot:nums[i], nums[boundary] = nums[boundary], nums[i]boundary += 1nums[boundary], nums[hi] = nums[hi], nums[boundary]return boundary def quick_sort(nums, lo=0, hi=None):hi = len(nums) - 1 if hi is None else hiif lo < hi:p = partition(nums, lo, hi)quick_sort(nums, lo, p - 1)quick_sort(nums, p + 1, hi) a = [5, 2, 4, 1, 3]quick_sort(a)print(a) # [1, 2, 3, 4, 5]Step 1 of 7· line 3
The pivot is the last item, 3. Everything before boundary will be smaller than it.
- compared with
One partition: O(n). Quick sort: O(n log n) on average, O(n²) ; on average.
When you'll use it
- Sort Colors, “move all X to the front”, k-th largest element (), sorting in place without extra arrays.
In the wild · Every “Sort by” button: Sorting a spreadsheet by price, then by name, needs a stable sort, which is why Python and JavaScript both use merge-sort-based TimSort.
Common mistakes
- Always taking the last item as the pivot on already-sorted input: O(n²). Pick a random one.
- Off-by-one around the pivot: recurse on lo … p − 1 and p + 1 … hi, never including p again.