JavaScript Insertion Sort

Insertion Sort is a simple algorithm. Many start learning sorting algorithms with Insertion Sort. The idea is to take elements one by one (from left to right) and to place them in such a way that traversed part of the array is sorted:

  • Take 2nd element and check if it smaller than 1st. If yes then swap. Now first 2 elements are sorted
  • Take 3rd element and check if it smaller than 2nd or 1st. Place in such a way that first 3 elements will be sorted
  • Take 4th ...
function insertionSort(arr){
  // Init variables
  var i, j, key;

  // Loop through array
  for (j = 1; j < arr.length; j++){
    key = arr[j];
    i = j - 1;

    // Move values so that key can be placed in right position
    while(i >= 0 && arr[i] > key){
      arr[i+1] = arr[i];
      i -= 1;
    }

    // Put key in its place
    arr[i+1] = key;
  }
  return arr;
}