Insertion sort is a simple sorting algorithm. Though it may not be much efficient for a larger input size, it has some advantages. Like it has a simple implementation. Jon Bentley showed a three-line version in C programming language. It is also more efficient the bubble sort or selection sort. It is an adaptive and stable algorithm.
This is the second day of the 30 days of algorithm series. In the last day, we discussed the bubble sort. You can check that too!
How Insertion Sort Works?
Insertion sort works in the way as we sort playing cards in our hand during a card game. We assume that the first card in our hand is sorted. Now if the card dealer deals a new card we put it either upon the previous card or below the previous card.
In this similar approach, insertion sort puts an element in its right place at each iteration. Consider we have the following list to sort. While sorting in ascending order we’ll try to get an overview of how the insertion sort works.
We assume that the first element, \(50\) is sorted. So we go to the second element, \(12\). We compare it with the first element. If it is smaller we swap the first and the second elements.
Now the first two elements are sorted. So we go to the third element and compare it with all the elements left of it and place it after the element just smaller than it. This procedure continues until we get the sorted list.
The Insertion Sort Algorithm
The pseudocode is as following. The array is 0-based indexed.
Implementation
Here the algorithm has been implemented using python.
Complexity Analysis
For the first element, there is only 1 comparison, for the second element, it is 2 comparisons. Then the number of comparisons are 3, 4, 5, ….,(n-3), (n-2), (n-1) accordingly till the last element. So the total number of comparisons are:
\(1 +2 +3 + … + (n-3) + (n-2) + (n-1) = \frac{n(n-1)}{2} \approx n^2\)
So the complexity is \(O(n^2)\). This can be deduced from the number of loops also. There are two loops; one of them is nested. So the complexity is \(n * n = n^2\); thus, \(O(n^2)\).
Time complexities:
- Worst case complexity: \(O(n^2)\)
If the list is in descending order and we want to sort it in ascending order then the worst case occurs. - Best case complexity: \(O(n)\)
If the list is already sorted in the desired order then the best case occurs. In this case the outer loop runs for \(n\) times. - Average case complexity: \(O(n^2)\)
If the list is in jumbled order, an average case occurs.
Space complexity:
Space complexity is \(O(1)\) because only one extra variable is used.
Applications of Insertion Sort
Insertion sort is used when a simple implementation is needed and there is a smaller list to sort. If there is any situation where only a few elements are left to be sorted, this algorithm can be used.
