Insertion Sort

Insertion sort works like sorting playing cards in your hand. Keep the left part of the list sorted. Take the next item and slide it left past every larger item until it fits.

It is O(n squared) in the worst case, but on a list that is already nearly sorted it is close to O(n), which makes it a good choice for small or almost-sorted data. Real libraries often use it for tiny sections.

Examplepython

Open in editor »

Quick check

When is insertion sort especially fast?

When the list is nearly sorted alreadyWhen the list is huge and randomWhen all items are text

Your turn: write the code

Sort the list from largest to smallest using insertion sort (change the comparison) and print it.

Finish the quick check (and any code exercise) to complete this lesson, or mark it done yourself.

Tip: use the left and right arrow keys to move between lessons.