INSERTION SORT

Insertion can be compared to sorting a hand of cards as you draw from the top of a deck. The unsorted array is the deck and the sorted array is your hand. The first element will be the first card in your hand and each subsequent element is a new card that you draw and add to your hand in its correct order.

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

• The first element of the array will be the first element in the sorted array.
• The rest of the array will be considered the unsorted array.
• The for loop starts at the second index which is assigned the identifier current.
• The while loop then compares arr[current] the element to its left arr[j].
• If arr[current] is less than the element to its left, it swaps places with that element.
• Then arr[current] is compared to the new element that is now on its left.
• This repeats as long as there is an element to the left of arr[current] that has a greater value.
• If arr[current] is greater than the element to its left, it stays where it is.
• Then the for loop starts over with the next element in the unsorted array and repeats the process.
• Once the for loop has gone through the whole unsorted array, the sorted array is returned.