Insertion sort, explained

Insertion sort works the way many people sort cards. You pick up one card at a time and slide it into the right place among the cards you already hold.

The left part of the list is always sorted. Each new item is moved left until it finds its position.

How it works

• Start with the first item, which is a sorted list of one.
• Take the next item and compare it with the sorted items on its left.
• Shift bigger items one place to the right until the right gap appears, then put the item there.
• Repeat until every item has been inserted.

A small example

Sort this list:

5 2 4 6 1 3

Insert 2:  2 5 4 6 1 3
Insert 4:  2 4 5 6 1 3
Insert 6:  2 4 5 6 1 3   (already in place)
Insert 1:  1 2 4 5 6 3
Insert 3:  1 2 3 4 5 6

What to know about its cost

• Best case O(n) on a sorted list.
• Average and worst case O(n²).
• Uses O(1) extra space and is stable.

Where it works well

• Excellent on small or nearly sorted lists.
• Works as the list arrives, one item at a time.

Where it struggles

• Slow on long, badly ordered lists.
• An item far from its place needs many shifts.

Try it yourself

Open the Sorting experiment, enter the list 5 2 4 6 1 3, choose Insertion Sort and step through it. Then use the comparison view to run another algorithm on the same list and compare the comparisons and swaps.

Open the Sorting experiment