Bubble, Insertion & Selection Sort

The 10-second versionCopy Anchor Link

These are the three sorts you can write from memory after five minutes of thinking. Bubble sort repeatedly swaps neighbours that are out of order. Selection sort repeatedly finds the smallest remaining element and drops it into place. Insertion sort grows a sorted prefix by sliding each new element back to where it belongs, the way you sort a hand of cards. All three are O(n²) in the worst case, all three sort in place, and all three are still genuinely useful — insertion sort is the finishing move inside almost every real sorting library.

Why this existedCopy Anchor Link

Sorting predates computers. People sorted punched cards, mail, and inventory by hand with schemes that look like these algorithms, so when the first stored-program machines arrived, these were the methods people already knew — handed around the field until nobody could say who "invented" them. They're folklore: algorithms that emerged from practice before anyone wrote them down.

• 1956 — The name "bubble sort" first appears in print (in an ACM paper), describing an "exchange sort" that was already in common use. The algorithm is older than the name — the signature of folklore.
• 1960s — Insertion sort gets its canonical description as the "sorting a hand of cards" model, and becomes the textbook first algorithm.
• Selection sort's appeal was always its predictability: even before you run it, you know exactly how many comparisons are coming — no surprises, no data dependence.

Why they mattered then: on a machine with a few kilobytes of memory and no library, a sort you could reason about at a glance was worth more than a clever one you couldn't. Why they matter now: they're the base case. Production sorts recurse down to about sixteen elements and then finish with insertion sort, because on tiny, nearly-sorted runs it beats everything more clever.

Inside the inventor's headCopy Anchor Link

Imagine you've never seen a sorting algorithm and someone hands you a shuffled deck. What do you actually do?

The card-player's instinct is the right one: you pick up cards one at a time and slide each new card into its spot among the ones you're already holding. At every moment your left hand is sorted, and you never re-check it. That's insertion sort, and it's the model the others are measured against.

The naive first attempts are where it gets fun. "Compare every pair and swap if needed" gives you bubble sort — correct, but it marches the biggest element to the end on every pass, so it burns one full pass per element. "Scan everything for the smallest, then everything again, then again" gives you selection sort — correct, but it does the same number of comparisons whether the input is random, sorted, or backwards, because it throws away the order it just observed.

The pivot for insertion sort is realizing you don't need to re-scan: each new element is already almost in place, so you only slide it back over the elements that are genuinely bigger than it. On data that's already close to sorted, that's almost no work at all.

// Naive: always do all n-1 passes, even if the array is already sorted.function bubbleNaive(a) {  for (let i = 0; i < a.length - 1; i++)    for (let j = 0; j < a.length - 1 - i; j++)      if (a[j] > a[j + 1]) [a[j], a[j + 1]] = [a[j + 1], a[j]];}// Improved: if a pass makes no swaps, we're done — O(n) on sorted input.function bubbleEarly(a) {  for (let i = 0; i < a.length - 1; i++) {    let swapped = false;    for (let j = 0; j < a.length - 1 - i; j++)      if (a[j] > a[j + 1]) {        [a[j], a[j + 1]] = [a[j + 1], a[j]];        swapped = true;      }    if (!swapped) break;  }}

The final approachCopy Anchor Link

Insertion sort — the one to actually learnCopy Anchor Link

Walk i from 1 to the end. The prefix a[0..i) is sorted. Take a[i] and slide it left past every element bigger than it, then drop it in. The prefix is now one longer, and still sorted.

The invariant: at the top of each outer iteration, a[0..i) is a sorted copy of the i elements originally in a[0..i). The slide step inserts a[i] into that sorted prefix without disturbing anything else, so the invariant holds for i + 1.

Selection sort and bubble sort, brieflyCopy Anchor Link

• Selection sort — the invariant is that a[0..i) holds the i smallest elements in final position. Find the minimum of the rest, swap it into slot i.
• Bubble sort — the invariant is that after pass k, the last k elements are the k largest in final position. Each pass bubbles the biggest remaining element to the end.

A worked trace: insertion sortCopy Anchor Link

Sorting [5, 2, 4, 6, 1, 3]:

Notice step 3: when the data is already in order, insertion sort does one comparison and moves on. That adaptability is the whole reason it survives today.

It in codeCopy Anchor Link

function insertionSort(a) {  for (let i = 1; i < a.length; i++) {    const key = a[i];    let j = i - 1;    while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; }    a[j + 1] = key;  }  return a;}function selectionSort(a) {  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;    [a[i], a[min]] = [a[min], a[i]];  }  return a;}function bubbleSort(a) {  for (let i = 0; i < a.length - 1; i++)    for (let j = 0; j < a.length - 1 - i; j++)      if (a[j] > a[j + 1]) [a[j], a[j + 1]] = [a[j + 1], a[j]];  return a;}

ComplexityCopy Anchor Link

"Adaptive" means the running time improves on partially-sorted input. Selection sort never adapts — it always does the same comparisons, which is exactly why it feels rigid next to insertion sort. It's also unstable: swapping a distant minimum into place can jump an element past an equal one.

Where you meet it todayCopy Anchor Link

• Every major sort library. std::sort, Java's Arrays.sort, and Rust's sort all cut over to insertion sort for small ranges (typically under ~16 elements), because the overhead of the fancy algorithm isn't worth it there.
• Nearly-sorted data. TimSort (used by Python and Java) detects existing sorted runs and stretches them with insertion sort before merging. Your "almost sorted" logs are the best case, not a special case.
• Tiny fixed collections. Sorting a handful of items in an embedded system or a lookup table is faster with two nested loops than with any recursive machinery.
• Online input. Keeping a short array sorted as items arrive is insertion sort, and it's the natural way to maintain a small priority list.

// Insert x into an already-sorted array, keeping it sorted.function insertSorted(a, x) {  let i = a.length;  a.push(x);  while (i > 0 && a[i - 1] > x) { a[i] = a[i - 1]; i--; }  a[i] = x;}

RecapCopy Anchor Link

• Insertion sort models sorting a hand of cards: grow a sorted prefix, slide each new element into place. It's adaptive and stable.
• Selection sort is predictable but rigid — the same comparisons no matter what, and unstable.
• Bubble sort is mostly a teaching tool, but with the early-exit flag it becomes adaptive and is O(n) on already-sorted input.
• All three use O(1) extra space and are unbeatable on tiny or nearly-sorted inputs, which is why libraries still call them.

Next up: Merge Sort — the first algorithm that guarantees O(n log n) and makes divide and conquer real.