Insertion Sort

Spotting one

The data is small, or already nearly in order, or it arrives one item at a time and has to stay sorted as it comes.

That last case is the one that matters in real systems. Insertion sort is what you use when you cannot wait for all the data before you start.

The idea, plainly

Exactly how most people sort a hand of cards. Keep a sorted group on the left. Take the next card, slide it left past everything bigger, drop it in. Repeat.

On nearly sorted data each card barely moves, which is why it is quick there and slow almost everywhere else.

Where to start

Insert into Sorted Array first. Placing one item correctly is the whole inner step.

Implement Insertion Sort then repeats it across the list.

Count Insertion Sort Shifts is more useful than it looks. The number of shifts is exactly the number of pairs that were out of order to begin with, which is a real measure of how unsorted the data was.

Insertion Sort List moves it onto a linked list, where there is no shifting at all. You unlink a node and relink it, which is cheaper than moving everything along in an array.

Sort a Nearly Sorted Array is the honest ending. Insertion sort copes, and a small heap copes better. Knowing when your method stops being the right one is worth as much as knowing the method.

Common mistakes

Swapping neighbours over and over instead of shifting along and dropping the item in once. It gets there and it writes far more than it needs to. Repeated neighbour swapping is bubble sort, not this.

Comparing against items on the right, which have not been sorted yet. Only the left side is in order.

Reaching for it on large, randomly ordered data, where it is genuinely slow.