DAY 8 / 30 · WEEK 2 · PART 3 OF 3

Insertion Sort

Part 1: Bubble Sort · Part 2: Selection Sort · Insertion Sort (here)

Goal of the day

• Implement insertion sort from scratch: grow a sorted prefix one element at a time.
• Understand why it's the only one of Day 8's three sorts with a genuine O(n) best case on nearly-sorted data.
• Recognize its signature: no swapping — elements shift to make room, then the key drops into the gap.

Concept

This is how most people actually sort a hand of playing cards: pick up one new card at a time, and slide it into its correct spot among the cards you've already arranged. Everything to the left of the card you're holding is already sorted — you just need to find where the new one fits, shifting bigger cards one slot to the right to make room, and dropping the new card into the gap. Repeat until every card has been picked up once.

Diagram

Interactive visualization

The code

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j]; // shift bigger elements right
      j--;
    }
    arr[j + 1] = key; // drop the key into its now-open slot
  }
  return arr;
}

Line by line:

• No swapping at all. Bigger elements shift one slot right to make room, and the key drops into the gap left behind — this is exactly the "sort cards in your hand" motion.
• The while loop is what gives insertion sort its O(n) best case: on an already-sorted array, arr[j] > key is false immediately, so the loop never runs and the key just stays where it is.

Dry run: insertionSort([5, 2, 8, 1])

i=2 needed zero shifts because 8 was already bigger than everything to its left — that's the O(n) best-case behavior showing up even mid-array, not just for a fully-sorted input.

Complexity

Of Day 8's three sorts, insertion sort is the one real sorting libraries actually reuse — many O(n log n) sorts (including some Day 10 merge sort implementations) switch to insertion sort for small sub-arrays, since its low constant factor and O(n) best case make it faster in practice below a certain size.

Interview corner

• Why does insertion sort matter more than bubble sort in practice? Its O(n) best case is genuinely useful for small or mostly-sorted inputs — some real sort implementations switch to insertion sort for small sub-arrays inside a bigger O(n log n) sort.
  ↳ Common follow-up: "So why not just always use insertion sort?" — its worst case (reverse-sorted data) is still O(n²) with a lot of shifting, and for large, unpredictable data an O(n log n) sort (Day 10/11) wins decisively.
• How is insertion sort different from selection sort (Part 2), given both build a sorted prefix? Selection sort builds the prefix by repeatedly finding the global minimum of what's left. Insertion sort builds it by taking the next element in original order and finding where it belongs among what's already sorted — no scanning ahead required.
  ⚠ Trap: don't confuse "grows a sorted prefix" (true of both) with "does the same work" (false) — insertion sort's cost depends on how unsorted the input already is; selection sort's doesn't.
• What determines how many shifts a single insertion costs? How far the key has to travel to reach its correct position among the already-sorted elements to its left — a key that's already bigger than everything before it costs zero shifts; a key that belongs all the way at the front costs a shift for every element in the sorted prefix.

How to talk through it out loud: state the invariant — "after step i, the first i elements are fully sorted relative to each other." Then connect it to the best case explicitly: "if the array is already sorted, this invariant is trivially maintained with zero shifts per step, which is where the O(n) best case comes from."

Practice problems

// O(n) version, appropriate for today. O(log n) binary search
// version is Day 12 material — the array is already sorted here,
// which is exactly what binary search needs.
function searchInsert(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] >= target) return i;
  }
  return nums.length;
}

function removeElement(nums, val) {
  let write = 0;
  for (let read = 0; read < nums.length; read++) {
    if (nums[read] !== val) {
      nums[write] = nums[read];
      write++;
    }
  }
  return write;
}

// Array-based sketch of the idea (real linked-list version on Day 15):
function insertionSortArray(arr) {
  const result = [];
  for (const val of arr) {
    let i = 0;
    while (i < result.length && result[i] <= val) i++;
    result.splice(i, 0, val); // insert val at position i
  }
  return result;
}

Quiz