An Introduction to Insertion Sort

This blog post is a continuation of a series of blog posts about Algorithms, as it has been a hard concept for me to grasp as a programmer. Feel to check out the first blogpost about Algorithms, where I provide an introduction of what Algorithms are and an example of an algorithm and the second blog post about Data Structures, where I explained what are Data Structures and what are some types of Data Structures. Also check out the third blog post about Time Complexity and Space Complexity, which I provide an explanation of Time and Space Complexity. I have also written a blog post about Big O Notation. Recently I have written blog posts about Binary Search, Linear Search, Interpolation Search, Sorting Algorithms, and Selection Sort.

This blog post I will focus on Insertion Sort. I will explain what is Insertion Sort, how is Insertion Sort associated with Algorithms, try to break down the concept of Insertion Sort step by step and provide an example.

What is Insertion Sort and how is it associated with Algorithms?

Insertion sort is a sorting algorithm, which sorts the array by shifting the elements one at at time. It iterates the input elements by growing the sorted array at each iteration. It compares the current element with the largest value in the sorted array. If the current element is greater, then it leaves the element in its place and moves on to the next element else it finds its correct position in the sorted array and moves it to that position. This is done by shifting all the elements, which are larger than the current element, in the sorted array to one position ahead

Insertion Algorithms: Steps on how it works:

1. If it is the first element, it is already sorted.
2. Pick the next element.
3. Compare with all the elements in sorted sub-list.
4. Shift all the the elements in sorted sub-list that is greater than the value to be sorted.
5. Insert the value.
6. Repeat until list is sorted.

Below is an array of 4 numbers, which need to be sorted. We will use Insertion Sort Algorithm, to sort this array:

Since 7 is the first element and has no other element to be compared with, it remains at its position. Now when on moving towards 4, 7 is the largest element in the sorted list and greater than 4. So, move 4 to its correct position, which is before 7. Similarly with 5, as 7 (largest element in the sorted list) is greater than 5, move 5 to its correct position. Finally for 2, all the elements on the left side of 2 (sorted list) are moved one position forward as all are greater than 2 and then 2 is placed in the first position. Finally, the given array will result in a sorted array.

Insertion Sort: An example

Here is an example of writing the Insertion Sort Algorithm based on the steps I provided earlier. Below I have written a function, which accept the following parameter: an array. The function returns the sorted array.

Important Characteristics of Insertion Sort:

• It is efficient for smaller data sets, but very inefficient for larger lists.
• Insertion Sort is adaptive, that means it reduces its total number of steps if given a partially sorted list, hence it increases its efficiency.
• Its space complexity is less. Insertion sort requires a single additional memory space.
• Overall time complexity of Insertion sort is O(n2).

Overall Insertion Sort is an important concept to understand when it comes to algorithms. Thank you for reading this blog post. In upcoming blog posts of this series, I will go over other sorting algorithms.