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