The simple sorts

Why learn sorts nobody uses

Your language has a sort, and it is better than anything you will write. These three are here because they are the clearest examples of a complexity argument you can hold in your head — and because insertion sort is genuinely used, inside the sort your language ships.

All three are O(n²) comparisons and O(1) extra memory. What separates them is how many times they move data, and how they behave when the input is already nearly in order.

Selection sort — the fewest moves

Find the smallest of what is left, put it at the front, repeat. It always makes exactly n(n−1)/2 comparisons — whatever the input, sorted or not — and at most n−1 swaps.

That last property is its only real advantage: when a write is far more expensive than a read (flash memory, a network round trip per move), the sort that moves each item at most once wins. It is also not stable: the long-distance swap can jump one equal item over another.

for (let i = 0; i < a.length - 1; i++) {
  let min = i;
  for (let j = i + 1; j < a.length; j++) if (a[j] < a[min]) min = j;
  if (min !== i) [a[i], a[min]] = [a[min], a[i]];
}

Bubble sort — the one to know is bad

Swap neighbours that are out of order, repeatedly, until a whole pass makes no swaps. With the swapped flag it detects sorted input in one pass — O(n) best case — but on random data it does the most data movement of the three and is comfortably the slowest.

It is stable, it is in place, and there is no situation in which it is the best choice. Its value is educational: the n² is visible in two nested loops that anyone can see.

let swapped = true;
for (let end = a.length - 1; end > 0 && swapped; end--) {
  swapped = false;
  for (let j = 0; j < end; j++) {
    if (a[j] > a[j + 1]) { [a[j], a[j + 1]] = [a[j + 1], a[j]]; swapped = true; }
  }
}

Insertion sort — the one that is actually used

Keep the front of the array sorted and insert each new item into its place — the way you sort a hand of cards. On already-sorted input the inner loop never runs, so it is O(n); on nearly-sorted input it is O(n + inversions), which is close to linear.

It is stable, in place, and its constant factor is tiny. That is why every serious sort — Timsort, introsort, V8’s — switches to insertion sort once a partition gets down to about ten items: below that, O(n²) with a small constant beats O(n log n) with a big one.

for (let i = 1; i < a.length; i++) {
  const value = a[i];
  let j = i - 1;
  while (j >= 0 && a[j] > value) { a[j + 1] = a[j]; j--; }   // slide, do not swap
  a[j + 1] = value;
}

Measured, on the same input

"Best case n" means already sorted. That is not a technicality — real data is very often nearly sorted, which is exactly what Timsort was built to exploit.