Algorithms - Sorting (Insertion Sort)

insertionSort.js

/*
    Insertion sort 
    - Time complexity O(n^2)
    - Best use case if data is nearly sorted and if new random data is added to the array to be sorted
*/

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        // Pick second element in the array
        let currentVal = arr[i];
        // Compare that to the element before and swap if necessary
        // In this case, we are also checking if the element before is greater than the current value
        for (var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
            // Assign arr[j] to the next index because it is greater than current value
            arr[j + 1] = arr[j];
        }
        // Finally insert current value in the correct place
        arr[j + 1] = currentVal;
    }

    return arr;
}

insertionSort([3, 23, 67, 2, 5, 76, 54, 90, 102, 4, 7, 32, 13]);