Module P-8·11 min read

Bubble, selection, and insertion sort — why they're O(n²), and why understanding them still matters.

Written by Jatin Jain Saraf · Architect of SupraScan

Module P-8 — Sorting I: O(n²) Sorts and Why They're Slow

What this module covers: Before the two sorts that actually get used in production (Modules P-9, P-10), it's worth building — and clearly seeing the cost of — the three sorts everyone encounters first: bubble, selection, and insertion. All three are O(n²), all three are correct, and understanding exactly why they're O(n²) is what makes merge sort and quick sort's O(n log n) feel like a real, earned improvement rather than a magic number to memorize.

Bubble Sort: Repeatedly Swap Adjacent Out-of-Order Pairs

Bubble sort repeatedly scans the array, swapping any adjacent pair that's out of order — each full pass "bubbles" the largest remaining unsorted value to its correct position at the end.

function bubbleSort(nums: number[]): number[] {
  const arr = [...nums];
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // swap adjacent out-of-order pair
      }
    }
  }
  return arr;
}

The outer loop runs n times; the inner loop, for each outer iteration, checks roughly n more adjacent pairs. That's the identical nested-loop shape flagged as O(n²) back in Module F-1 — n × n comparisons in the worst case, each one only fixing a single adjacent pair before moving on.

Selection Sort: Repeatedly Find the Minimum

Selection sort takes a different approach to the same cost: on each pass, scan the entire remaining unsorted portion to find its minimum, then swap that minimum into its correct position.

function selectionSort(nums: number[]): number[] {
  const arr = [...nums];
  for (let i = 0; i < arr.length; i++) {
    let minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) minIndex = j; // track the smallest remaining value's index
    }
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; // one swap per outer iteration
  }
  return arr;
}

Same O(n²) shape, arrived at differently: n outer iterations, each doing an O(n) scan to find the minimum. The one practical difference from bubble sort worth naming: selection sort performs at most n swaps total (one per outer iteration), while bubble sort can perform up to O(n²) swaps — a real difference if swaps are expensive (say, swapping large objects rather than plain numbers), even though both are the same Big-O time class.

Insertion Sort: Build Up a Sorted Prefix

Insertion sort grows a sorted region from the left, inserting each new element into its correct position within that already-sorted prefix:

function insertionSort(nums: number[]): number[] {
  const arr = [...nums];
  for (let i = 1; i < arr.length; i++) {
    const current = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j]; // shift larger elements right to make room
      j--;
    }
    arr[j + 1] = current;
  }
  return arr;
}

Worst case (input in reverse order) is still O(n²) — each new element might need to shift all the way through the entire sorted prefix. But insertion sort has a property the other two don't: on already-nearly-sorted input, it's close to O(n), because the while loop barely runs at all when each new element is already close to its correct position. This isn't just a theoretical curiosity — it's exactly why some production sort implementations switch to insertion sort for small subarrays (often somewhere under 10-20 elements) even inside an otherwise O(n log n) algorithm: below a certain size, insertion sort's low overhead and near-linear behavior on partially-ordered data beats the overhead of further recursive splitting.

Why All Three Are O(n²), and Why That's Worth Feeling, Not Just Knowing

// The shared bottleneck, made explicit: n outer iterations, each doing O(n) work
// Regardless of exactly what that O(n) work is (swap-scan, find-min, shift-insert),
// n × O(n) = O(n²) is unavoidable with this "local, incremental fix" strategy.