InsertionSort

This algorithm builds up the sort by gradually creating a larger left half which is always sorted.

InsertionSort Pseudocode

1. Start by picking the second element in the array.
2. Now compare the second element with the one before it and swap if necessary.
3. Continue to the next element and if it is in the incorrect order, iterate through the sorted portion  
(i.e. the left side) to place the element in the correct place.
4. Repeat until the array is sorted.

InsertionSort Implementation

JavaScript

function InsertionSort(arr){
    for(let i = 1; i < arr.length; i++){
        let currentVal = arr[i];
        for(let j = i-1; j >= 0 && arr[j] > currentVal ; j--){
            arr[j+1] = arr[j];
        }
         arr[j+1] = currentVal;
    }
    return arr;
}

Python

def insertion_sort(arr):
    for i in range(1, len(arr)):
        current_val = arr[i]
        j = i - 1
        while j >= 0 and current_val < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = current_val
    return arr

Time Complexity: Big(O)

Worst case: O(N^2)