Insertion Sort

Build a Sorted Prefix by Shifting

1:00

How insertion sort grows a sorted prefix one element at a time by shifting larger elements right, why it is adaptive and stable, and when to use it.

By the end, you can

Explain the shift-and-drop move that defines insertion sort and trace it on a small array.
Identify which code line extracts the key, which shifts elements, and where the key is finally placed.
Trace all passes of insertion sort on a given array, counting shifts and comparisons per pass.
Derive the best-case O(n) and worst-case O(n²) complexities from the structure of the loops.
Explain why the strict greater-than shift condition makes insertion sort stable.
Define adaptive, in-place, and online, and give the insertion-sort example for each.
Compare insertion sort and selection sort on comparisons and writes, and identify when each is preferred.
Name the production sorting algorithms that use insertion sort as a subroutine for small subarrays.

Up next in Searching & Sorting