JavaScript Algorithms #3 - Insertion Sort

1. What is Insertion Sort?

Insertion sort is a simple sorting algorithm that builds up the sort by gradually creating a larger left half which is always sorted. Values from the unsorted part are picked and placed at the right position in the sorted part. Compared to more advanced algorithms such as quick sort or merge sort, insertion sort seems much less efficient because it builds the final sorted array one item at a time.

2. Insertion Sort Pseudo Code

1. Start sorting by picking the second element(index of 1) in the array.
2. Compare the second element with the one before it and swap if the first one is greater than the second one.
3. Continue to the next element and iterate through the sorted part if it is not in the correct order until it finds its correct place.
4. Repeat until the entire array is sorted.
   

   3. Implementing the Insertion Sort

function insertionSort(arr){
        for (let i = 1; i < arr.length; i++){
            let current = arr[i];
            let j = i - 1;
            while ((j >= 0) && (current < arr[j])){
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = current;
        }

        return arr;
    }

4. Time Complexity of the Insertion Sort

It takes four steps to complete the insertion sort: to delete, compare, shift and insert. In the worst case scenario, it takes N²/2(compare) + N²/2(shift) + N-1(delete) + N-1(insert) = N² + 2N - 2 stages, which equals to O(N²) in big O notation.