Insertion Sort

Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. For the 2nd, 3rd, 4th, etc. element: slide backwards into proper relative sorted position.

Insertion Sort

This sort works on the principle of inserting an element at a particular position, hence the name Insertion Sort.

Algorithm :

for i in 1 .. n-1
    current := a[i]
    j := i
    while (j > 0 and current < a[j-1])
        a[j] := a[j-1]
        j--
    a[j] = current 

Example :

30 64 26 46 109 21 84 98
30 64 26 46 109 21 84 98
26 30 64 46 109 21 84 98
26 30 46 64 109 21 84 98
26 30 46 64 109 21 84 98
21 26 30 46 64 109 84 98
21 26 30 46 64 84 109 98
21 26 30 46 64 84 98 109  

Notes :

1. O(N^2) time complexity in worst, and average cases.
2. O(N) time complexity in best case if input is already sorted or nearly sorted.
3. If data is reversed, this algorithm is worst.
4. After pass k, the first k+1 elements are in relative sorted order
5. Lees comparisons than selection sort, but has more swaps than selection sort.
6. Better than selection sort if moves are cheap; worse if expensive.
7. It is stable and in-place sorting algorithm.

Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.