Bubble, selection and insertion sort

All three are O(n²). They differ in what they do with each pass, and one of them earns its place in real libraries.

Bubble sort

Repeatedly swap adjacent out-of-order pairs; the largest element bubbles to the end each pass.

function bubbleSort(a) {
  for (let end = a.length - 1; end > 0; end--) {
    let swapped = false;
    for (let i = 0; i < end; i++) {
      if (a[i] > a[i + 1]) { [a[i], a[i + 1]] = [a[i + 1], a[i]]; swapped = true; }
    }
    if (!swapped) return a;    // already sorted: O(n) best case
  }
  return a;
}

Teaching value only. It does the most swaps of the three and is never the right choice.

Selection sort

Find the minimum of the unsorted part, swap it into place. Exactly n−1 swaps — the fewest of any comparison sort.

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;
    if (min !== i) [a[i], a[min]] = [a[min], a[i]];
  }
  return a;
}

Its niche is real but narrow: when a write is far more expensive than a comparison, such as wearing out flash memory. It is not stable, and it never finishes early.

Insertion sort

Take the next element and slide it back into its correct place among the already-sorted prefix — the way people sort a hand of cards.

function insertionSort(a) {
  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--];
    a[j + 1] = value;
  }
  return a;
}

This one matters. It is stable, in-place, adaptive — O(n) on nearly-sorted input — and its inner loop is so tight that it beats O(n log n) sorts on small arrays.

That is why real implementations of quicksort and merge sort stop recursing at around 10–16 elements and finish with insertion sort. Asymptotics decide the algorithm; constants decide the base case.