Reviewing Sorting Algorithms: Insertion Sort
Let’s sort it out!
In a series of posts, we will be discussing some of the sorting algorithms listed in the below order:
In this post, we will explore the next in a series of sorting algorithms, the Insertion Sort. If you are still wondering how we landed here with a bunch of sorting algorithms, please go through the previous posts on Bubble Sort and Selection Sort. We are yet to discover the fastest and most efficient algorithm to sort the long list of input elements. In this post, the question remains, is Insertion Sort "The One"? We don’t have to wait for the "Oracle" to confirm. Let’s find out.
Why is it called Insertion Sort?
Insertion Sort is one of the simplest and easiest sorting algorithms to understand. By the way, when’s the last time you sorted a hand of playing cards? If it’s today, congratulations! You have understood insertion sort even before we started. Brownie points to you!! If it’s been a while, you should try forming the thinking cloud of sorting the playing cards. You might have not realized it; you were implementing a version of the Insertion Sort algorithm to quickly sort the cards at hand. Well, if you are one of those, who never sorted playing cards, there isn’t a better time than “now” to expedite your understanding of the Insertion Sort.
Remember, in our pilot post of Bubble Sort, we discussed sorting as an act of arranging the elements systematically, based on a predetermined order or certain rules. We have observed from our previously discussed sorting techniques that a comparison of elements is the fundamental idea to arrive at a sorted list. In the case of the Insertion Sort, the basic principle is of inserting an unsorted element at a particular sorted position. The name “Insertion Sort” is derived based upon the concept, where an element has to find its rightful place and has to be inserted in there. If you are confused, let’s go through the below listed instructions to get some clarity.
Breaking down the instructions:
For a given unsorted array [10,4,8,6,1], the iteration will be performed for every array element, from left to right.
Two subsets or sub-lists are maintained, the left side is a sorted subset and the right side is an unsorted subset. The first element in the array [10,4,8,6,1] will remain in place and is assumed to be sorted, as there are no further elements on the left side to compare.
Now we have two sections, one sorted section , and other unsorted sections [4,8,6,1]. Insertion Sort will iterate through each element of the unsorted list and compare it with the sorted subset, to shift the largest number to the right and insert the smallest element in its current rightful sorted position.
The first element in the unsorted subset (i.e., 4 in our example) is compared against each element from the sorted subset (i.e., 10 in this case) for its rightful sorted position.
If a number in a sorted list is found to be greater than the unsorted list number (i.e., 4), the number is shifted one position right. Meaning, the smaller number is inserted into the sorted subset. Result array would be [4,10,8,6,1].
The sorting will iterate to the next number (i.e., 8) to compare against a new sorted subset [4,10]. The above steps will be repeated until a valid sorted position is obtained for the same number.
In the next iteration the sorted subset is [4,8,10], the process is repeated for the next number in an unsorted subset [6,1]. We observe that the unsorted subset shrinks with every iteration.
Let’s play with our numbers:
Problem: Sort the given array [10, 4, 8, 6, 1]. As discussed above, we will divide the array into two subsets of sorted and unsorted lists to demonstrate subsets. Iteration starting with the first index  as below.
For more insight into Step 4, below is a simple demonstration.
Observations based on Iterations:
Well, the obvious observation here is, in each iteration, we compared the first unsorted item against the sorted item to its left to figure out if it’s in the right sorted position.
Iteration is performed on every element and it is from left to right, growing the sorted array. Although the first element is unsorted, it becomes the sorted element in the first iteration.
If the current unsorted array element is smaller than the sorted array element, the current element is shifted to one place higher than its current position.
The array size in our example is n = 5 and the total iterations performed will be (n-1).
The total number of comparisons required to sort: n = 5 elements is (n-1) + (n-2) + (n-3) + (n-4). You might recognize the similar pattern from Selection Sort.
In case of a completely sorted list, the Insertion Sort requires the same number of comparisons as that of an unsorted list. However, there will be no shifting or insertion of elements performed.
If there are duplicate elements in the sorting array, the Insertion Sort won’t move one element in front of the other, instead, the key value will be maintained in order. This characteristic makes the Insertion Sort a stable sorting algorithm. You may ask what is considered as stability in the sorting algorithm?