Insertion Sort

Insertion sort is the one your hands already know. It’s how you sort a hand of cards: keep the left side tidy, pick up the next card, and slide it back past everything that’s bigger until it sits in the right spot. Do that for every card and the whole hand is sorted.

What’s neat about insertion sort is it actually cares how messy your list is to start with. Give it something already sorted and each value just checks its neighbor once and stays put, so it’s one clean pass and done. Give it a reversed list and every value has to crawl all the way to the front, which is where the n² comes from. Try the Sorted and Reversed inputs and watch the comparison count go from tiny to huge. It’s also why the big sorts don’t recurse all the way down. Once the pieces are small and mostly in order, they just hand them off to insertion sort to finish.

Hit Play to watch it run, or use Next and Back to step one comparison at a time. Shuffle deals a fresh array, and the highlighted line shows you where the code is at each step.