SOURCE

function insertSorting(arr) {
    for (let i = 0; i < arr.length; i++) {
        // step1: 取出一个数，从已经排序好的元素中从后往前扫描
        const cur = arr[i];
        // prev 相当于就是我们的扫描指针
        let prev = i - 1;
        // step2 移动 prev 指针，直到 cur >= arr[prev] (需要考虑一下下标越界的情况)
        while (prev >= 0 && arr[prev] > cur) {
            // step3: 如果扫描到的元素大于cur，则需要继续向前扫描。并把arr[prev]向后移动一位,直到找到arr[i]的合适位置为止
            arr[prev + 1] = arr[prev];
            prev -= 1;
        }        
        // step4:找到合适位置了！ 在 prev + 1 处插入元素
        arr[prev + 1] = cur;
    }

    return arr;
}

console.log('insertSorting([2, 9, 6, 7, 4, 3, 1, 8])', insertSorting([2, 9, 6, 7, 4, 3, 1, 8]))