Implement Insertion Sort

Insertion sort is a sorting algorithm in which elements are transferred one at a time to their correct position. It can be considered as shifting around and inserting elements in their right order to sort an unsorted array of any size.

The array is searched sequentially on a fundamental level and unsorted items are moved and inserted into the sorted sub-list(in the same array).

This algorithm is not suitable for large data sets.

This algorithm has quadratic time complexity in the average and worst cases.

function insertionSort(array) {
  let j, i, key;
  let n = array.length;
   for(i=1;i<n;i++){
      key=array[i];
      j=i-1;
      while(j>=0 && array[j] > key){
        array[j+1]= array[j];
        j = j-1;
      }
      array[j+1] = key;
   }
  // Only change code below this line
  return array;
  // Only change code above this line
}