Algo VisualizedStart learning

Quicksort & Partitioning

Quicksort is the sort most standard libraries reach for first: it sorts in place and is usually the fastest in practice. Its partition step is also a tool you will reuse on its own.

intermediate⏱ 12 min read

←Builds on

2Merge Sort: Divide & ConquerQuicksort is divide and conquer too, but it does its work before the recursive calls, not after.1Prefix Sums, Two Pointers & Sliding WindowPartitioning is two pointers walking toward each other and swapping misplaced elements.

Leads to→

2Comparators & Stabilitystd::sort is an introsort built around quicksort's partition.
1Learn2Play3Check4Practice
01

Learn

The idea, the mechanics and the cost.

01Partition around a pivot

Quicksort is divide and conquer with the work done before the recursion instead of after:

  • Choose a pivot element, here the last one of the range.
  • Partition: rearrange so everything smaller than the pivot is on its left and everything else on its right.
  • The pivot now sits in its final sorted position. Recurse on the left part and on the right part.

No merge step is needed: once both sides are sorted, the whole range is sorted, because every left element is already smaller than every right one.

before (pivot = last, 25)291037149311325after partition101491325312937< 25≥ 25final place

02Lomuto partition, step by step

The partition runs in one pass with two indices. Pointer i marks the end of the "< pivot" zone; pointer j scans the unseen elements.

  • If a[j] < pivot: swap a[i] and a[j], then i++. The small element joins the left zone.
  • Otherwise just move on; it stays in the "≥ pivot" zone.
  • At the end, swap the pivot into position i.

One pass, O(n) comparisons, no extra array: quicksort sorts in place, using only the recursion stack.

Hoare's partition (two pointers moving towards each other) does fewer swaps and handles many equal keys better; a three-way partition (<, =, >) is best when there are lots of duplicates.

< pivot≥ pivotnot seen yetpivoti ↓j ↓a[j] < pivot → swap(a[i], a[j]), i++

03Good pivots, bad pivots

If the pivot lands near the middle, each partition splits the range roughly in half: log n levels of O(n) work, O(n log n), just like merge sort.

If the pivot is always the smallest or largest value, one side is empty and the other has n − 1 elements. The recursion becomes a chain of depth n and the total work is n + (n−1) + … + 1 = O(n²). With "last element as pivot", that happens on already sorted input, which is very common in real data.

The fix is to pick the pivot at random (or the median of three). Then no particular input is bad, and the expected time is O(n log n) on every input. Production sorts like introsort also switch to heapsort if the recursion gets too deep.

good pivot: depth log nbad pivot: depth ne.g. on already sorted input

04Quicksort vs merge sort, and quickselect

Quicksort wins in practice on arrays: it works in place, scans memory sequentially and has small constants. Merge sort wins when you need stability or a hard worst-case guarantee. Quicksort is not stable.

The partition idea also solves a different problem. To find the k-th smallest element, partition once: if the pivot lands at index k, you are done; otherwise recurse into only one side. Expected work n + n/2 + n/4 + … = O(n). This is quickselect, available as std::nth_element.

Use it for medians, "top k" and percentiles when you do not need the whole array sorted.

Cost at a glance

Average / random pivotO(n log n)
Worst case (bad pivots)O(n²)
One partitionO(n)
Extra memory (stack)O(log n)
Quickselect (k-th element)O(n) expected

Remember

  1. Partitioning puts the pivot in its final place with smaller elements left and larger right, in one O(n) pass.
  2. Balanced pivots give O(n log n); always picking the min or max gives O(n²), so choose the pivot randomly.
  3. Quicksort is in place and fast but not stable; quickselect reuses partition to find the k-th element in O(n).
02

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Watch i (end of the small zone) and j (the scanner). Each "place" step freezes one pivot forever. Try 10 20 30 40 50 60 to see the bad case.

Interactive visualizerfocus here, then space ← →
✎ Your inputUp to 10 numbers, 1–99. Try one already sorted, or sorted backwards.

Quicksort (Lomuto partition) · partition range [0, 7]

29
10
14
37
13
25
9
31
Quicksort: pick a pivot, partition so smaller elements sit left and larger right, then recurse. 8 elements, pivot = last of each range.

Pseudocode

 1 quicksort(lo, hi): 2   pivot = a[hi]; i = lo 3   for j in lo..hi-1: compare a[j] with pivot 4     if a[j] < pivot: swap a[i],a[j]; i++ 5   swap a[i],a[hi]  // pivot reaches final spot 6   recurse on [lo,i-1] and [i+1,hi]
1 / 1
03

Check

Three questions. Pick an answer to see why.

Q1

Lomuto partition of [7, 2, 9, 4, 5] with pivot 5 (the last element). Where does 5 end up?

Q2

Quicksort with "last element as pivot" is given an already sorted array of n elements. What happens?

Q3

You need the median of 10⁷ numbers, once. What is the best tool?

04

Practice

Real problems to lock it in, easiest first.

LeetCodeSort Colors intermediate↗LeetCodeSort an Array intermediate↗LeetCodeKth Largest Element in an Array intermediate↗LeetCodeTop K Frequent Elements intermediate↗