Algorithms: Insertion sort

Next algorithm I want to learn more about is the Insertion sort algorithm. This algorithm works like we humans sort playing cards by hand.

This algorithm works by building a sorted portion of the array one element at a time. For each step in an array we do the following.

In this example we can have the mind visualisation as follows.

We start by picking up cards one by one
We place each card in the correct position relative to the others we have already sorted.

Key takeaways of Insertion sort:

It can be inefficient for larger datasets
We have repeated comparisons. For each element, comparisons are repeated even if unnecessary in larger arrays.

So now when we understand the basics of Insertion sort and the complexity that comes with it we must practice this together.

Here is some basic -> Expert exercises for Insertion Sort

Comparison with other sorting algorithms

Algorithm	Time Complexity (Best)	Time Complexity (Worst)	Space Complexity	Stable?
Selection	$O(n^2)$	$O(n^2)$	$O(1)$	No
Bubble	$O(n)$ (optimized)	$O(n^2)$	$O(1)$	Yes
Insertion	$O(n)$	$O(n^2)$	$O(1)$	Yes
Merge	$O(n \log n)$	$O(n \log n)$	$O(n)$	Yes
Quick	$O(n \log n)$	$O(n^2)$	$O(\log n)$	No

Sign up for Andreas Jangefalk