Quick Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Quick Sort

Choose a pivot, partition the array around it, recurse on each side. Average O(n log n) with tiny constants — the default sort in many languages.

How it works

Quick Sort flips the merge sort idea: instead of doing trivial split + heavy combine, it does heavy split (partition) + trivial combine (nothing).

1. Pick a pivot (often the last or middle element).
2. Partition the array so that everything < pivot is to its left and everything > pivot is to its right.
3. Recurse on each partition (the pivot is now in its final position).

The Lomuto partition scheme is shown here for clarity. The Hoare partition is faster in practice but harder to get right.

Quick Sort's magic: it sorts in place, the constant factors are tiny, and the partition step has excellent cache behavior. The catch is that a bad pivot choice degrades to O(n²) — the next three articles fix this.

Complexity

Interactive visualization

Pseudocode

procedure quickSort(A, lo, hi):
  if lo < hi:
    p ← partition(A, lo, hi)
    quickSort(A, lo, p − 1)
    quickSort(A, p + 1, hi)

procedure partition(A, lo, hi):
  pivot ← A[hi]; i ← lo − 1
  for j from lo to hi − 1:
    if A[j] ≤ pivot: i ← i + 1; swap A[i], A[j]
  swap A[i + 1], A[hi]
  return i + 1

JavaScript implementation

function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo < hi) {
    const p = partition(arr, lo, hi);
    quickSort(arr, lo, p - 1);
    quickSort(arr, p + 1, hi);
  }
  return arr;
}
function partition(arr, lo, hi) {
  const pivot = arr[hi];
  let i = lo - 1;
  for (let j = lo; j < hi; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]];
  return i + 1;
}

Pros and cons

When to use it

• General-purpose in-memory sort when stability isn't required.
• Standard library default in C's qsort, std::sort, Java primitive sort.
• Pairs naturally with introspective fallbacks (IntroSort).