Day 8c: Insertion Sort

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

Day 8 covers three O(n²) sorts in three short parts: Bubble Sort → 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

Running example: arr = [5, 2, 8, 1, 9, 3]

Press Play or Step to begin.

Step 0 / 26

▶ Play⏭ Step↺ Reset🔀 Shuffle

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	key	Shifts	Array after
1	2	5 shifts right	[2, 5, 8, 1]
2	8	none — 8 > 5 is false immediately	[2, 5, 8, 1]
3	1	8, 5, 2 all shift right	[1, 2, 5, 8]

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

Time (best)	Time (worst)	Space	Stable?
O(n) — already sorted, no shifts	O(n²)	O(1)	Yes

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

1. Search Insert Position

Easy — LeetCode: Search Insert Position

Given a sorted array and a target, return the index where the target is found, or where it would be inserted to keep the array sorted.

Show hint

This is literally “find where to insert” — today’s core operation. A simple linear scan works now; binary search (Day 12) gets this to O(log n) once that pattern is in your toolkit.

Show solution

// 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;
}

2. Remove Element

Easy — LeetCode: Remove Element

Remove all occurrences of a value from an array in place, and return the new length.

Show hint

This is Day 4’s read/write two-pointer shape again — only write forward when the current element should be kept.

Show solution

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;
}

3. Insertion Sort List

Medium — LeetCode: Insertion Sort List

Sort a linked list using insertion sort. (A preview — we build linked lists properly on Day 15. For now, just think through the approach in terms of arrays.)

Show hint

Exactly today’s algorithm — walk the input one element at a time, and insert each into its correct position in a growing sorted result. The “shift right” step looks different on a linked list (relink pointers instead of moving array slots), but the core idea is identical.

Show solution

// 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

1. Which sort has the best BEST-CASE time complexity on a nearly-sorted array?

Bubble sort — same as the othersSelection sortInsertion sort

2. How does insertion sort move elements out of the way?

Shifting — no swapping at allSwapping pairs, like bubble sortIt doesn’t move any elements

3. Is insertion sort stable?

YesNo

4. Where do real sorting libraries often still use insertion sort?

As a fallback for small sub-arrays inside a bigger O(n log n) sortNowhere — it’s purely a teaching toolAs the primary sort for huge datasets

5. How does insertion sort choose which element to place next, compared to selection sort?

It just takes the next element in original order — no scanning aheadIt scans ahead to find the global minimum, same as selection sortIt picks randomly

---

← Part 2: Selection SortDay 9: Recursion & the Call Stack →