Skip to content

level 3 · Sorting

Quick Sort

Pick a pivot, split around it, and let the halves sort themselves.

11 min 90 XP

what is it

Start here

Quick sort plays a game of 'bigger or smaller?'. It picks one value — the pivot — and shoves everything smaller to its left and everything bigger to its right.

After that one pass, the pivot is in its final position forever, even though nothing else is sorted yet. That's the clever part: you don't sort the list, you just get one value home and split the problem in two. Then you play the same game on the left half and the right half.

On average it's as fast as merge sort — n log n — but it does its shuffling in place, with no second array. That's why it's the sort most language libraries actually use under the hood. Its one weakness: pick unlucky pivots every time and it degrades to n². Real implementations dodge that by choosing the pivot cleverly.

real-life analogy

Picture it

Sorting a pile of exams by picking one at random

You grab one exam and call out its score. Everyone with a lower score, go left of it; higher, go right. Now that one exam is exactly where it belongs, and you've turned one big pile into two smaller piles. Repeat on each pile. You never compared the far-left exams with the far-right ones — the split saved you all that work.

interactive visualization

Watch it run

The pink bar is the pivot. Watch smaller values jump to its left.

  1. 8
  2. 3
  3. 5
  4. 1
  5. 9
  6. 2
  7. 7
  8. 4

Quick sort picks one value as a pivot, then shoves everything smaller to its left and everything bigger to its right. The pivot lands in its final home — then it does the same to each side.

step 01/33

  • comparing
  • moving
  • in final place
1function quickSort(a, lo = 0, hi = a.length - 1) {
2 if (lo >= hi) return a;
3 const p = partition(a, lo, hi);
4 quickSort(a, lo, p - 1);
5 quickSort(a, p + 1, hi);
6 return a;
7}
8
9function partition(a, lo, hi) {
10 const pivot = a[hi];
11 let i = lo;
12 for (let j = lo; j < hi; j++) {
13 if (a[j] < pivot) {
14 [a[i], a[j]] = [a[j], a[i]];
15 i++;
16 }
17 }
18 [a[i], a[hi]] = [a[hi], a[i]];
19 return i;
20}

variables right now

Nothing in play yet — press play.

comparisons 0moves 0

the dry run · every step, in words

33 steps

complexity

What it costs

best case
O(n log n)
average
O(n log n)
worst case
O(n²)
extra memory
O(log n)

Average case splits the list roughly in half each time: n log n. Worst case — a pivot that's always the smallest or largest value — splits off just one item at a time and collapses to n². Good pivot choice is what keeps it fast in practice.

  • O(1)
  • O(log n)
  • O(n)
  • O(n log n) · this one
  • O(n²)
input size →work →

common mistakes

Common traps

  • Always choosing the first or last element as the pivot.

    On an already-sorted list that's the worst possible pivot every time, giving O(n²). Pick a random element, or the median of three, to stay fast.

  • Forgetting to put the pivot in its final place after partitioning.

    After the loop, swap the pivot into the boundary position. Skip that and the pivot never actually lands where it belongs.

  • Recursing on ranges that include the already-placed pivot.

    The pivot is done — recurse on lo..p−1 and p+1..hi, never on p itself, or you'll loop forever.

  • Believing quick sort is always faster than merge sort.

    On average it usually is, and it uses less memory. But merge sort's worst case is still n log n; quick sort's is n². Which is 'better' depends on whether you can tolerate a bad day.

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+90 XP

01After one partition step, what is true about the pivot?

02When does quick sort degrade to O(n²)?

03What does quick sort have that merge sort doesn't?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.