Insertion & selection sort

Two more O(n²) sorts — one shines on nearly-sorted data, one minimises writes. · 7 min read

Insertion sort grows a sorted prefix: take the next element and slide it left into place, like sorting a hand of cards. It's O(n²) worst case but O(n) on nearly-sorted input — the go-to for small or almost-ordered arrays.

Interactive visualization: Insertion sort — step through it frame by frame on this page.

Selection sort is bubble's mirror image: each pass scans the unsorted tail for the minimum and swaps it into place. It always makes exactly n−1 swaps — handy when writes are expensive — but always does O(n²) comparisons, even on sorted input.

Interactive visualization: Selection sort — step through it frame by frame on this page.