InsertionSort

const insertionSort = (arr)=>{
    let time = Date.now(); 
    for(let i=1;i<arr.length;i++)
    {
        let j = i-1; 
        while((j>=0) && (arr[i] < arr[j]))
        {   
            arr[j+1] = arr[j];
            j--;
        }
        arr[j]  = arr[i];
        
    }
    console.log(`Time taken = ${(Date.now()-time)/1000} seconds`);
    return arr;
}
let array = Array.from({length:10000000},(x,i)=>Math.floor(Math.random()*i));

console.log(insertionSort(array));
//insertion sort better than selection and bubble sort . the latter two take more than 13 seconds, while insertion takes less than 1 second to sort 10*size of array for bubble & insertion