Insertion sort works by looking at each element within a list (starting with the second element) and comparing it with the item before. If the item before is larger, they are swapped. This continues until the item is smaller at which point we do the same for the next element in the list.
Insertion sort isn’t all that bad.. as long as you use it in the right circumstances.
The time complexity of this algorithm, at worst case, is quadratic — O(n²). As n approaches infinity the average case approaches the worst case divided by two. However since if your list is sorted or nearly so, it can be O(n) in a best case scenario and thus well adapted to that scenario.
As mentioned above it can be fast under certain circumstances. Consider the array [6, 7, 8, 9, 5 ], when using an algorithm like merge sort we would still need to split all the items and then merge them back up. With insertion sort we just need to verify that [6, 7, 8, 9] are in the correct ‘sorted so far’ order, then we shift all of them up one index for 1.
Because insertion sort is an adaptive sort, it also makes it an ‘online algorithm’, which means we can start sorting before we get all the items and then merge the lists once the partial sorting has completed.
Next up? Merge sort. One of the most widely used sorting algorithms in browsers today.
Having worked across sites raking in over 50 billion website visits annually, Michael Mitrakos can help your business to crush the web game with an award winning website.
I also created Wanderlust Extension to discover the most beautiful places across the world with highly curated content. Check it out!