Quicksort

Partition, then recurse

Merge sort does its work on the way back up, in the merge. Quicksort does its work on the way down, in the partition — and that is why it needs no merge step and no extra array.

After a partition the pivot is exactly where it belongs in the finished array, with everything smaller to its left and everything larger to its right. Neither side ever has to look at the other again.

function quickSort(a, lo = 0, hi = a.length - 1) {
  if (lo >= hi) return a;

  const p = partition(a, lo, hi);     // the pivot is now in its FINAL place
  quickSort(a, lo, p - 1);
  quickSort(a, p + 1, hi);

  return a;
}

Lomuto partition

One pass, one boundary index, O(1) extra memory. It is the easiest partition to get right, and the one to learn first. Hoare’s two-pointer version does fewer swaps and is what production code uses, but it does not leave the pivot in its final position, which makes it harder to reason about.

function partition(a, lo, hi) {
  const pivot = a[hi];               // the last element, for now
  let i = lo;                        // the boundary: everything before i is < pivot

  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]];     // put the pivot at the boundary
  return i;
}

The pivot decides everything

The worst case is not exotic. Taking the last element as the pivot makes already-sorted input the worst case, and already-sorted input is extremely common — which is how this becomes a production incident rather than an exam question.

Median-of-three is the usual fix: cheap, deterministic, and it makes sorted and reverse-sorted input the best case instead of the worst.

Pivot choice	On random input	On already-sorted input
Last element	n log n	n² — every partition is empty on one side
Random element	n log n	n log n, with overwhelming probability
Median of first, middle, last	n log n	n log n, and no extra randomness needed
True median (medians of medians)	n log n guaranteed	n log n, with a constant nobody wants

Against merge sort

Quicksort is usually the faster of the two in practice because it moves data within one array and the processor loves that. Its two weaknesses — the quadratic worst case and the lack of stability — are exactly why real libraries do not ship it plain.

	Quicksort	Merge sort
Average	n log n, small constant	n log n, larger constant
Worst	n²	n log n
Extra memory	O(log n) stack	O(n)
Stable	No	Yes
Cache behaviour	Excellent — partitions in place	Good

What a real library actually runs

Introsort (C++ std::sort): quicksort, but it counts its own recursion depth and switches to heapsort past 2·log n. Quicksort speed, with an n log n guarantee.
Timsort (Python, Java objects, V8): merge sort that finds runs already in order and uses insertion sort on short ones. Stable, and O(n) on nearly-sorted data.
Insertion sort at the bottom: every one of them stops recursing at about ten items and finishes with insertion sort.
Three-way partition when duplicates are likely: < = > rather than < >, so a million copies of the same value sort in one pass instead of quadratically.

Partition, then recurse

Lomuto partition

The pivot decides everything

Against merge sort

What a real library actually runs

Practice