What is Insertion Sort Algorithm?

Insertion sorting is one of the sorting techniques that is based on iterating the array and finding the right position for every element. It compares the current element to the predecessors, if the element is small compare it with the elements before. Move ahead to all greater elements making space for the swapped element.

Working of Insertion Sort

Consider an example array, arr = [ 64, 25, 12, 22, 11]

Step 1: Traverse array using for loop with variable i.

[ 64, 25, 12, 22, 11]  // Original array

Step 2: For i = 0 i.e. first index there will be no changes in the array as it is the first element.

[ 64, 25, 12, 22, 11] // key = 64, i = 0

Step 3: For i = 1, store the value as a key and check if the previous elements are greater or not. if so, swap the key with all other greater predecessors.

[ 64, 25, 12, 22, 11] -> [25, 64, 12, 22, 11]  // key = 25, i = 1

Step 4: As the value at index 3 i.e. 12 is smaller than all predecessors they all be swapped with 12 using another for loop that runs from i-1 to 0 index in the reverse direction.

[25, 64, 12, 22, 11] -> [25, 12, 64, 22, 11] -> [ 12, 25, 64, 22, 11]  // key = 12, i = 2

Step 5: Now for i = 3 i.e. 22 only 2 predecessors are greater hence it will be swapped backward up to 2 positions only as shown.

[ 12, 25, 64, 22, 11] -> [ 12, 25, 22, 64, 11] -> [ 12, 22, 25, 64, 11]  // key = 22, i = 3

Step 6: Now, for the last index, as it is the smallest element of the array so using for loop it will be swapped back to the 0 index with the help of a temporary variable key.

 [ 12, 22, 25, 64, 11] ->  [ 12, 22, 25, 11, 64]  ->  [ 12, 22, 11, 25, 64]  -> [ 12, 11, 22, 25, 64]  -> [11,  12, 22, 25, 64]  // key = 11, i = 4

Programmatic Approach for Insertion Sort

• For sorting an array using insertion sort first iterate the array using for loop and always keep the current element in a temp varaible or key in this case.
• Now at every iteration compare the key value to all previouse element, in case key value is greater do nothing, but in case it is smallar swap back all predecessors till the value reaches at right position i.e. left one should be smallar and right one should be greater.
• Complete all iteration with along with above mentioned steps and return the final sorted array.

Example:

Original array: 64,25,12,22,11
After sorting: 11,12,22,25,64

Conclusion

Insertion sort is a simple and easy to understand algorithm that works on iterating and comparing the value with predecessors and swap the value with all the greater element. Time complexity of Insersion sort in O(N²) and auxilary space required is O(N). Basically, Insertion sort is efficient for small data values. Insertion sort is adaptive in nature, i.e. it is appropriate for data sets that are already partially sorted.