pick a pivot

#the idea

an empty list, or a list with one item, is already sorted. that's the base case. for anything longer:

1. pick one item, the pivot.
2. split the rest into the ones smaller than the pivot and the ones bigger.
3. sort both sides the same way, and put them back together: smaller, pivot, bigger.

neither side is sorted after the split, but everything is on the right side of the pivot, so sorting each side finishes the job. it's divide and conquer again: split until every piece is a base case.

function quicksort(list) {
  if (list.length < 2) return list;
  const pivot = list[Math.floor(Math.random() * list.length)];
  const smaller = list.filter((n) => n < pivot);
  const equal = list.filter((n) => n === pivot);
  const bigger = list.filter((n) => n > pivot);
  return [...quicksort(smaller), ...equal, ...quicksort(bigger)];
}
 
quicksort([33, 10, 15, 7, 40, 21, 3]); // [3, 7, 10, 15, 21, 33, 40]

#the pivot matters

say you always pick the first item instead. on a random list, that's fine: 40,000 numbers took 22ms. now hand it a list that's already sorted. the first item is the smallest, so every split leaves nothing on one side and everything else on the other. instead of halving the list, each level takes one item off, and there are as many levels as items.

on a sorted list of 10,000 numbers, that version ran out of stack: Maximum call stack size exceeded. with a random pivot, the same list sorted in 7.7ms. a random pivot makes that bad split very unlikely. on average quicksort is O(n log n). the O(n²) worst case still exists, it just almost never shows up.

#in real life