Let’s sort it out!
In a series of posts, we will be discussing some of the sorting algorithms listed in the below order:
Insertion Sort
Quick Sort
Heap Sort
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 [10], 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 [0] 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?
Defining Stability
Insertion Vs Selection Vs Bubble Sort
Time and space complexity are listed in the below table:
Code Implementation:
Log Output:
Let’s check the log output to understand the case of a fully sorted array and unsorted array.
Unsorted array: There are two loops performed, one is the outer loop for array iteration, and another is the inner loop for comparisons. At the start of the sorting, the first element (10) is considered as a sorted subset and the inner loop will compare the first unsorted element (4) against the sorted element. As the unsorted array shrinks on every iteration, the sorted array inner loop keeps growing to shift the elements. The inner loop will run for (n-1) elements wherein ‘n’ is the total number of array elements. For instance, for the last iteration in the test case, the array index [4] = 1 element is compared against (n-1) = 4 sorted array elements. If you observe closely, the inner loops iterate from right to left to compare against the sorted array list. The double looping is what makes the Insertion Sort worst-case time complexity О(n^2) because if the input doubles the running time will be quadratic.
Sorted array: In test case 3, the log shows no inner loops, as the values are already sorted. However, the comparisons are performed to check the rightful sorting position. Insertion Sort requires ‘n’ steps to sort an already sorted array of ‘n’ elements, which makes its best-case time complexity a linear function of O(n).
Final thoughts
So next time you sort out cards manually or play bridge, remember it’s an Insertion Sort. It is yet another simple algorithm that is slow due to its internal looping. In all fairness, Insertion Sort has an edge over its peers Bubble and Selection Sort as it has a best-case running time for an already sorted array list. Moreover, it is a stable algorithm with in-place properties and the ability to sort a list as it is received.
We have arrived at the most awaited conclusion, the Insertion Sort is not “The One” we were looking out for. Well, our quest to find “The One” continues and looks like we are getting really close. In the next post, we shall discuss “Merge Sort” to continue our pursuit of finding the most efficient sorting algorithm.
Stay tuned!!
I hope you enjoyed the post. Please subscribe to ProstDev for more exciting topics.
Hasta luego, amigos!
Study Resources
Below are some resources which discuss Insertion Sort and its Time-Space complexity at length.
[Video] Insertion Sort - CS50 Harvard
A Comparative Study of Selection Sort and Insertion Sort Algorithms Fahriye Gemci FuratResearch Assistant, Department of Computer Engineering, Iskenderun Technical University, Hatay, Turkey
Great post Vishal! I like this algorithm more than the other 2, but still not the most efficient :D