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

  1. boundary = 0. 5 isn't < 3, skip. 2 is: swap it to the boundary → [2, 5, 4, 1, 3], boundary 1.
  2. 4 isn't < 3, skip. 1 is: swap it to the boundary → [2, 1, 4, 5, 3], boundary 2.
  3. 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.

pivot ← last item, boundary ← first index
for each other item:
if item < pivot: swap it to boundary, boundary ← boundary + 1
swap the pivot to boundary(its final place)
quick sort: do the same to the left part and the right part

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]

05
▲ boundary
12
24
31
43
pivot = 3boundary = 0

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 < pivot
for i in range(lo, hi):
if nums[i] < pivot:
nums[i], nums[boundary] = nums[boundary], nums[i]
boundary += 1
nums[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 hi
if 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.

Practise it · before the Sorting problems

Partition around a pivot

Rearrange nums so every number smaller than comes first, then every number equal to it, then every larger one. Keep each group in its original order.

Input nums = [9, 12, 5, 10, 14, 3, 10], pivot = 10

Output [9, 5, 3, 10, 10, 12, 14]

Input nums = [-3, 4, 3, 2], pivot = 2

Output [-3, 2, 4, 3]

Pass every test and this concept is marked as known on the roadmap and on every problem that needs it.

Your code

Tab / Shift+Tab indent · ⌘/Ctrl+/ comments · ⌘/Ctrl+Enter runs · Esc leaves the editor

Stuck?