Insertion sort

In insertion sort, we compares adjacent elements and swap them, if they are out of order. We take the next element and insert into the sorted list that we maintained in the beginning of the array and repeats the procedure on it and so on.

Advantages: 

Insertion sort provides several advantages

• Insertion sort takes advantage of pre-sorting
• Simple implementation
• Efficient for small data sets
• Stable: does not change the relative order of elements with equal keys
• O(1) extra space
• O(n²) comparisons and swaps
• Adaptive: O(n) time when nearly sorted
• Very low overhead
• Online: New elements can be added during the sort

 

Simulation:

We demonstrate the insertion sort with an array of integers.

• Grey indicates the elements which are already sorted.
• Black indicates the element which is being inserted (key).

key

At any stage, the insertion sort has an unsorted array of integers.

• We begin with the first element that is 24. Since it is only one element, we consider the sorted list of length 1. 

• Next we insert element 13 which is on the second place. 

Comparing 13 and 24, we see that they are out of place, so we swap them. Now, we have sorted array of 2 elements.

• We move on to insert the third element which is 9.

Comparing 9 and 24, we see that they are out of order, so we swap them.

Now, comparing 9 and 13, we see that they are out of order swap, so we swap them, too. Now, we have sorted array of 3 elements.

• We move on to insert fourth element which is 64.

Comparing 64 and 24, we see that elements are in order. So, our fourth element is on its place. Now, we have sorted array of 4 elements.

• Going on to insert the fifth element, we have 7.

Comparing 7 and 64, we see that they are of order, so we swap them. In fact, 7 is smallest element so far, so it will move on to the beginning of the array. Now, we have 5 sorted elements.

 

 

 

• Moving on towards the sixth element, we have 23.

This is smaller than 64 and 24, so it gets inserted before those. We have six sorted elements.

• We move on towards seventh element which is 34.

34 is smaller than 64, but bigger than 24, so it gets inserted between them.

• Now, we have all the elements sorted except the last one which is 47.

47 is smaller than 64, but bigger than 34, so it gets inserted between them.

Algorithm:

Explanation of Algorithm:

We use an array for illustration. Beginning the insertion sort, we start with the first element in the sorting list. Since, there is no element in the list to compare with. So, we can consider it is sorted and i is initializes with 1 and goes to length[A]-1 in for loop. The value in i is the key element with which comparison has to make with its presorted elements of the array. If the value in key is smaller than its previous element in the sorted array, then swap them. Otherwise, leave them as they are. Repeat this process with each element of the array. In general, we inserted successive elements by swapping with the one before it, until we reach a smaller element. The resultant array is in ascending order.

To sort in descending order, just replace A[key] < A[key-1] to A[key] > A[key-1] in line number 3 of algorithm.

Running time:

Worst case performance	O(n2)
Best case performance	O(n)
Average case performance	O(n2)
Worst case space complexity	O(n) total, O(1) auxiliary

Reference:

• Introduction to Algorithms by Thomas Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein

Feel free to comment with your questions and suggestions regarding the post content...!