Insertion Sort in Python
Introduction
If you’re majoring in Computer Science, Insertion Sort is most likely one of the first sorting algorithms you have heard of. It is intuitive and easy to implement, but it’s very slow on large arrays and is almost never used to sort them.
Insertion sort is often illustrated by comparing it to sorting a hand of cards while playing rummy. For those of you unfamiliar with the game, most players want the cards in their hand sorted in ascending order so they can quickly see which combinations they have at their disposal.
The dealer deals out 14 cards to you, you pick them up one by one and put them in your hand in the right order. During this entire process your hand holds the sorted “subarray” of your cards, while the remaining face down cards on the table are unsorted – from which you take cards one by one, and put them in your hand.
Insertion Sort is very simple and intuitive to implement, which is one of the reasons it’s generally taught at an early stage in programming. It’s a stable, in-place algorithm, that works really well for nearly-sorted or small arrays.
Let’s elaborate