Insertion Sort

Insertion sort is also a polynomial time complexity sorting algorithm which works in O(N²).

GeeksForGeeks: Insertion Sort

It is similar to how we insert playing cards in sorted order.
As the name suggests "insertion sort" checks the element from the beginning of the array if the element is larger than the current element in the array it moves to the next index otherwise if the element is less than the current element it swaps the positions and the next index is compared with the new value.

Algorithm:

for i = 1 to n-1:
insert the element in a sorted sequence in arr[0...(i-1)]

For example: 

arr = [2, 4, 3, 1, 5]

1.  i = 1, j = 0
    arr[i] = 4, arr[j] = 2
    arr[i] > arr[j] -> skip, j = j+1

    i = 1, j = 1
    i == j -> break, i = i+1

2.  i = 2, j = 0
    arr[i] = 3, arr[j] = 2
    arr[i] > arr[j] -> skip, j = j+1
    
    i = 2, j = 1
    arr[i] = 3, arr[j] = 4
    arr[i] < arr[j] -> swap, j = j+1
    
    updated arr = [2, 3, 4, 1, 5]
    i = 2, j = 2
    i == j -> break, i = i+1
    
3.  i = 3, j = 0
    arr[i] = 1, arr[j] = 2
    arr[i] < arr[j] -> swap, j = j+1
    
    updated arr = [1, 3, 4, 2, 5]
    i = 3, j = 1
    arr[i] = 2, arr[j] = 3
    arr[i] < arr[j] -> swap, j = j+1
    
    updated arr = [1, 2, 4, 3, 5]
    i = 3, j = 2
    arr[i] = 3, arr[j] = 4
    arr[i] < arr[j] -> swap, j = j+1
    
    updated arr = [1, 2, 3, 4, 5]
    i = 3, j = 3
    i == j -> break, i = i+1
    
4.  i = 4, j = 0
    arr[i] = 5, arr[j] = 1
    arr[i] > arr[j] -> skip, j = j+1
    
    i = 4, j = 1
    arr[i] = 5, arr[j] = 2
    arr[i] > arr[j] -> skip, j = j+1
    
    i = 4, j = 2
    arr[i] = 5, arr[j] = 3
    arr[i] > arr[j] -> skip, j = j+1
    
    i = 4, j = 3
    arr[i] = 5, arr[j] = 4
    arr[i] > arr[j] -> skip, j = j+1
   
    i = 4, j = 4
    i == j -> break, i = i+1

5.  i = 5 
    i == n -> stop

finally arr = [1, 2, 3, 4, 5] which is the required sorted sequence.

Code in Python: 

def insertion_sort(arr):
    n = len(arr)
    
    for i in range(1, n):
        x = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > x:
            # copy value of previous index to index + 1
            arr[j+1] = arr[j]
            # j = j - 1
            j -= 1
        # copy the value which was at ith index to its correct sorted position
        arr[j+1] = x

arr = [12, 11, 13, 5, 6]
print('Before sort arr: ',arr)
insertion_sort(arr)
print('Sorted arr: ',arr)

"""
Output:
Before sort arr:  [12, 11, 13, 5, 6]
Sorted arr:  [5, 6, 11, 12, 13]
"""

Time Complexity:

Insertion sort in the worst case is O(N²) when the array is sorted in reverse order.

Best case time complexity is O(N) when the array is already in sorted order.

Here is the code in C language: Insertion Sort in C

--
Have any questions or suggestions? Post in the comments below!!

By,

Anubhav Shrimal