Quick Sort

How quicksort works

Quicksort sorts by repeatedly partitioning. Given an array, pick one element as the pivot, then rearrange the array so everything smaller than the pivot is on the left, everything larger on the right. Now recursively sort the two sides — they're independent subproblems.

The two main steps:

1. Pivot selection. Pick an element to partition around. Common choices: first element (simplest, worst case prone), random element (good in expectation), median of three (industrial default).
2. Partition. Rearrange so elements ≤ pivot land on the left, elements > pivot land on the right. The pivot ends up in its final sorted position. The classic Lomuto and Hoare partition schemes both run in O(n) time and O(1) extra memory.
3. Recurse. Apply quicksort to the left subarray and right subarray. The pivot stays put.

Because each recursive call works in-place on a subrange of the original array, quicksort uses O(log n) total memory just for the recursion stack — far better than merge sort's O(n) auxiliary array.

Why is it so fast in practice?

Three reasons quicksort routinely beats other O(n log n) sorts on real hardware:

• Cache locality. Partitioning sweeps through contiguous memory — the kind of access pattern modern CPUs prefetch perfectly.
• Low constant factors. The inner loop of partition is just two pointer comparisons and a swap. No allocation, no extra arrays, no comparisons against null sentinels.
• Hot-input speedup. Real-world data is rarely truly random; quicksort's behavior on slightly-sorted or clustered data is excellent because the partition tends to be balanced.

The O(n²) worst case

If the pivot is consistently the smallest or largest element, partitioning peels off one element per recursion. The recursion depth becomes O(n) and each level still does O(n) comparison work — total O(n²). This happens when:

• You pick the first element as pivot, and the input is already sorted.
• You pick the last element as pivot, and the input is reverse-sorted.
• An adversary crafts an input specifically to defeat your pivot strategy.

Real-world quicksort implementations dodge this with one of three strategies: random pivot (cheap, robust), median-of-three (deterministic, fast), or "introsort" — start as quicksort, fall back to heapsort when recursion exceeds 2 × log₂(n). Introsort gets quicksort's speed with merge sort's worst-case guarantee, and is the basis for C++'s std::sort and Rust's older sort.

Quicksort vs merge sort

	Quicksort	Merge sort
Time (average)	O(n log n)	O(n log n)
Time (worst)	O(n²)	O(n log n)
Space	O(log n)	O(n)
Stable	No	Yes
Cache-friendly	Yes	No
Best for	In-memory random data	Linked lists, external sort, stability

Pseudo-code (Lomuto partition)

function quickSort(arr, lo, hi):
    if lo < hi:
        p = partition(arr, lo, hi)
        quickSort(arr, lo, p - 1)
        quickSort(arr, p + 1, hi)

function partition(arr, lo, hi):
    pivot = arr[hi]    # rightmost as pivot
    i = lo - 1
    for j from lo to hi - 1:
        if arr[j] <= pivot:
            i++
            swap arr[i] and arr[j]
    swap arr[i + 1] and arr[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;
}

Python implementation

def quick_sort(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if lo < hi:
        p = partition(arr, lo, hi)
        quick_sort(arr, lo, p - 1)
        quick_sort(arr, p + 1, hi)
    return arr

def partition(arr, lo, hi):
    pivot = arr[hi]
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
    return i + 1

Python's sorted() uses Timsort, not quicksort. If you want quicksort behavior in Python, you usually want it for educational reasons; for production sorting, the standard library is better.

Practical notes

• Choose a good pivot. The most common production strategy is median-of-three: take arr[lo], arr[mid], arr[hi], use the median of the three as the pivot. Cheap, robust, no randomness needed.
• Tail-call elimination. Recurse on the smaller partition; loop on the larger one. This caps recursion depth at O(log n) even for adversarial inputs.
• Cut off to insertion sort for small subarrays (n < ~16). Insertion sort beats quicksort on tiny arrays because of much lower overhead.
• Three-way partitioning (Dutch national flag): split into < pivot, == pivot, > pivot. Wins big when there are many duplicate keys, since equal elements are skipped instead of recursed into.