Insertion Sort Explained

Tom Luxton
Nov 3 · 2 min read

Insertion Sort is another sorting algorithm I will be going over in this series. It is a relatively simple one, that builds one element at a time. The algorithm works very similar to how a person would sort a hand of cards.

Say you have 5 cards and you want to order them in ascending order, from left to right. Below is an unsorted array of numbers that represent cards and their rank (assume they are of the same suit):

[1, 4, 5, 3, 2]

First, compare the two leftmost cards to check if they are in ascending order. If they are not: reorder them by switching them around. Else leave it be.

[ 1, 4, 5, 3, 2]

Then check the 3rd card from the left (2nd if you count 0th index) and compare it to the card to the left of it.

[1, 4, 5, 3, 2]

If it is bigger than leave it be, and you do not need to compare this to any further left as they are already ordered. In this case 5 is greater than 4 so we leave it be, and move rightwards to the next element.

[1, 4, 5, 3, 2]

In this case 3 is less than 5 so they are switched:

[1, 4, 3, 5, 2]

3 is less than 4, so they switch:

[1, 3, 4, 5, 2]

And 3 is greater than 1 so it remains where it is. The next index is compared and moved accordingly to the algorithm. Each step being showed here:

[1, 3, 4, 5, 2]

[1, 3, 4, 2, 5]

[1, 3, 2, 4, 5]

[1, 2, 3, 4, 5]

Since this is the last index, the algorithm returns the sorted array:

[1, 2, 3, 4, 5]

Pseudo code:

insertionSort(arr)
for i <- 2 to length(arr)
do key <- arr[i]
j <- i - 1

while j > 0 and arr[j] > key
arr[j + 1] <- arr[j]
j <- j - 1
arr[j + 1] <- key
return arr

Algorithm Performance:

Time Complexity of Insertion Sort is O(n^2). As the worst case scenario would be when the array is in complete wrong order and therefore each element (n) is compared to every other element (n) therefore n*n = O(n^2).

Worst case space complexity is О(n) total, O(1) auxiliary. n being the array of n size.

Find out more

If you want to learn more about algorithms, I just posted an article about Bucket Sort , or you can get the MIT published book on Algorithms. I use this book to study for my Algorithms and Data structures course, and I absolutely think its the best one out there.


Originally published at https://tomluxton.com on November 3, 2019.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade