Quick Sort

Quick sort picks a pivot, moves every smaller value to its left and every larger one to its right, so the pivot lands in its final place — then sorts each side the same way.

Start

5
3
8
2
9
1
4
  • Pivot
  • Comparing
  • Moving
  • In final place
  • Outside this part

Quick sort picks a pivot, moves smaller values to its left and larger to its right, then sorts each side the same way.

Step 1 / 32
Comparisons
0
Swaps
0
quickSort(lo, hi):
  if lo ≥ hi: return
  pivot = a[hi]; i = lo
  for j from lo to hi − 1:
    if a[j] < pivot: swap(a[i], a[j]); i++
  swap(a[i], a[hi])   // pivot lands in place
  quickSort(lo, i − 1); quickSort(i + 1, hi)

What's happening?

  1. Take the last value of the range as the pivot.
  2. Walk through the range: each value smaller than the pivot is swapped into the growing "smaller" side.
  3. Swap the pivot just after the smaller side — it is now final — and repeat on the left and right parts.

Complexity

Time
O(n log n) on average · O(n²) worst case (bad pivots)
Space
O(log n) for the recursion

Where you'll meet it

The default in-place sort in many libraries (C's qsort, Java's sort for primitives uses a dual-pivot variant) because it is fast in practice and cache-friendly.

Common mistake

Always taking the last value as pivot on already-sorted data: every split is lopsided and it degrades to O(n²). Real implementations pick random or median-of-three pivots.

FAQ

What is the pivot?

The value the range is split around. After partitioning it sits exactly where it belongs in the sorted list.

Why is the worst case O(n²)?

If the pivot is always the smallest or largest value, each step removes only one value instead of halving the range.

Is quick sort stable?

No — partition swaps can reorder equal values.