Insertion Sort

#insertionsort #algorithms #datastructure #javascript

Insertion sort builds the final sorted array one item at a time by comparisons. works best on small datasets and is much less efficient than quicksort, mergesort.

My understanding on this is that insertion sort removes one item from the input array/list, finds the location it belongs within the sorted list, and inserts it there. it repeats until no input elements remain.

below is the solution, using a recursive approach:

const insertionSort = (arr, n) => {
    if(n > 0) {     //base case
        insertionSort(arr, (n - 1))

        let x = arr[n];
        let j = (n - 1);

        while (j >=0 && arr[j] > x) {
            //swap 
            arr[j+1] = arr[j];
            j = j - 1;
        }
        arr[j+1] = x;

        console.log(arr, '\n');
    }
}
const inputArr = [5,10,1,25];
insertionSort(inputArr, (inputArr.length - 1));  // [1, 5, 10, 25]

Worst/Average case: O(n^2)
However insertion sort is the fastest in sorting small datasets, even faster than quicksort. but terrible with large datasets.