Algorithms · Sorting

Quick Sort

The idea

Organising a bookshelf: pick one book, put everything thinner on the left and thicker on the right. That book is now exactly where it belongs and never moves again. Repeat the trick on each side with a new book.

The problem

Pick one item — the pivot. Move everything smaller to its left, everything bigger to its right. Now the pivot sits in its FINAL position forever, and two smaller problems remain: sort the left side, sort the right side. Do the same to each.

Why it's slow

On average quick sort is a rocket: good pivots halve the problem like merge sort, giving O(n log n) with no extra memory. But feed our last-element-pivot version an already-sorted or reverse-sorted list and every pivot ends up at an edge: nothing is halved, and it burns the full n(n-1)/2 comparisons — pure O(n²), as slow as bubble sort. Try it in the player with 5,4,3,2,1. Real implementations dodge this by picking pivots more cleverly.

Pseudocode

  1. pick the last item as the pivot
    Explain this line

    Our version always picks the last item — simple but gameable.

  2. walk j across the range, comparing each item with the pivot
    Explain this line

    Every item in the range gets exactly one comparison per pass.

  3. smaller than the pivot? swap it into the left zone
    Explain this line

    The "left zone" collects everything smaller than the pivot.

  4. finally swap the pivot just after the left zone — locked forever
    Explain this line

    The pivot lands between the zones — its final home.

  5. now do the same to the left side and the right side
    Explain this line

    Two smaller ranges remain; each gets its own pivot.

Complexity

Best Average Worst Space
O(n log n) O(n log n) O(n²) O(log n)

The gambler: usually as fast as merge sort with no merge buffers, but a bad pivot streak (like sorted input with our naive pivot) collapses it to quadratic.

Code

python 
def quick_sort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo >= hi:
        return a
    pivot, i = a[hi], lo
    for j in range(lo, hi):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    quick_sort(a, lo, i - 1)
    quick_sort(a, i + 1, hi)
    return a
java 
void quickSort(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    int pivot = a[hi], i = lo;
    for (int j = lo; j < hi; j++) {
        if (a[j] < pivot) {
            int t = a[i]; a[i] = a[j]; a[j] = t;
            i++;
        }
    }
    int t = a[i]; a[i] = a[hi]; a[hi] = t;
    quickSort(a, lo, i - 1);
    quickSort(a, i + 1, hi);
}
cpp 
void quickSort(std::vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int pivot = a[hi], i = lo;
    for (int j = lo; j < hi; ++j) {
        if (a[j] < pivot) std::swap(a[i++], a[j]);
    }
    std::swap(a[i], a[hi]);
    quickSort(a, lo, i - 1);
    quickSort(a, i + 1, hi);
}
javascript 
function quickSort(a, lo = 0, hi = a.length - 1) {
  if (lo >= hi) return a;
  const pivot = a[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (a[j] < pivot) {
      [a[i], a[j]] = [a[j], a[i]];
      i++;
    }
  }
  [a[i], a[hi]] = [a[hi], a[i]];
  quickSort(a, lo, i - 1);
  quickSort(a, i + 1, hi);
  return a;
}
dart 
void quickSort(List<int> a, [int lo = 0, int? hiOrNull]) {
  final hi = hiOrNull ?? a.length - 1;
  if (lo >= hi) return;
  final pivot = a[hi];
  var i = lo;
  for (var j = lo; j < hi; j++) {
    if (a[j] < pivot) {
      final t = a[i];
      a[i] = a[j];
      a[j] = t;
      i++;
    }
  }
  final t = a[i];
  a[i] = a[hi];
  a[hi] = t;
  quickSort(a, lo, i - 1);
  quickSort(a, i + 1, hi);
}

Quick check