Coding Challenge Practice - Question 37

The task is to implement an insertion sort which sorts an array of integers in ascending order, done in place.

The boilerplate code:

function insertionSort(arr) {
  // your code here
}

The insertion array works by assuming the first element is already sorted. Starting from index 1, store the value as key

let key = arr[i]
let j = i - 1

Compare it to the elements before it, shift all elements bigger than it to the right by one position and insert the key in the correct position

while(j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
arr[j + 1] = key

The operation is repeated until the array is sorted. The final code is:

function insertionSort(arr) {
  // your code here
  for(let i = 0; i < arr.length; i++) {
    let key = arr[i];
    let j = i - 1;

    while(j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }

    arr[j + 1] = key;
  }
}