# pick a pivot

2023-11-26 · 3 min read · #algorithms

Source: https://jopcmelo.com/writing/pick-a-pivot

[selection sort](/writing/pick-the-biggest-repeat) took 2.1s to sort 40,000 numbers on my machine. quicksort did it in 20ms. Tony Hoare came up with it in 1959, as a visiting student at Moscow State University, and [published it in 1961](https://en.wikipedia.org/wiki/Quicksort).

## 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.

*(sketch: seven numbers. 21 is circled as the pivot, and the others drop one by one into a pile of smaller numbers, 10, 15, 7 and 3, or bigger ones, 33 and 40. then it starts over)*

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](/writing/the-biggest-square-that-fits) again: split until every piece is a base case.

```javascript
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.

*(sketch: a sorted list split on its first item, over and over: an empty list on one side every time, the rest on the other, one level per item)*

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

you'll rarely write one. `Array.prototype.sort` sorted the same 40,000 numbers in 11.5ms, and since 2018 V8 [uses TimSort](https://v8.dev/blog/array-sort) for it, not quicksort. **the idea is what you keep**: pick something, split around it, and the pieces get small fast. the version from the first time I wrote this post is in [my algorithms repo](https://github.com/joaopcm/algorithms/blob/main/quicksort/index.js).