Insertion Sort is a simple sorting algorithm which sorts a list of values by inserting a value called key into an already sorted list. We will now discuss the algorithm of insertion sort, how it works, its advantages and disadvantages, its implementation in C along with its complexity analysis.
The Algorithm
function insertion_sort(int arr[], int N)
{
/* input is an array of elements
array indexing is from 0 to N-1, where N is the size of array
*/
for ( i = 1 to N-1 )
key = a[ i ]
j = i - 1
while a[j] > key AND j >= 0
insert key into the sorted subarray { a[0],a[1],a[2],....,a[j-1] } at its appropriate position
j = j - 1
end while loop
insert key into its final position
end for loop
}
How it works
 |
An illustration of how the insertion sort works
Image source : en.wikipedia.org |
Its working is quite simple. The first element is assumed to be sorted in itself and hence the subarray { a[0] } is a sorted array. Initialise your key with the first element in the remaining array, which in this case is a[1], i.e., the second element. Now we have to insert this key into its appropriate place in the sorted subarray { a[0] }. Next we move onto the third element and repeat the process. This will continue till the last element. Let's take an example to make it clear :
Consider an array : { 2 4 3 5 1 }
Initially,
Sorted subarray : { 2 }
key = 4
1st step
Sorted subarray : { 2 4 }
key = 3
2nd step
Sorted subarray : { 2 3 4 }
key = 5
3rd step
Sorted subarray : { 2 3 4 5 }
key = 1
4th step
Sorted subarray : { 1 2 3 4 5 }
Advantages of Insertion Sort
1. It has a very simple implementation.
2. It is adaptive - for a nearly sorted array, it takes linear time, that is, order of n, O(n).
3. It is efficient for small size of input data.
4. It is more efficient than bubble sort and insertion sort.
5. Its has very low space complexity - requires only single extra memory space.
6. It is stable - it does not change the relative order of two data elements if they are equal.
Disadvantages of Insertion Sort
1. It is inefficient for large data sets - it has a time complexity of O(n^2).
Complexity Analysis
 |
Animation of the insertion sort sorting a 30 element array
Image source : en.wikipedia.org |
Worst - case time complexity : O(n^2)
Best - case time complexity : O(n)
Average - case time complexity : O(n^2)
Space complexity : O(1) - for extra memory , O(n) - for storing the list
Implementation in C
