Insertion Sort is an algorithm used to sort an array or linked list considering one element (or node) at a time. This sorting algorithm is great for working with smaller sets of data and is easier to implement than quicksort or one of the more advanced sorting algorithms. In the worst case scenario, insertion sort has a time complexity of O(n²).
How it Works:
Imagine you have 12 beers on a table (lined-up). You want to arrange them in order from the least beer left to drink to the fullest beer glass (I know, real world situations). To do this, you will pick up the second beer from the left and compare it to the beer to its left. So, in essence, beer compared to beer. If beer is smaller than beer, they are swapped. Then, we pick up beer and compare it to each beer to its left and insert it in the proper place (shifting beers over as needed), beer (do the same thing, beer, and so on…
Here’s a nice little gif to illustrate (just imagine the boring number boxes are beers):
To help myself learn Python and continue to improve my Ruby prowess, I’ve coded implementations of insertion sort in both languages below.