Insertion sort - with recursion implementation.

insertion_sort.js

// Sort an array of integers.
// [1,4,1,9,5,10] => [1,1,4,5,9,10]
function _insert(array, position, value) {
  var i = position - 1; // Check the previous value

  // Walk backwards in the array and shifts the values of the array
  // when the previous value is larger than the value we want to insert
  while ((i >= 0) && (array[i] > value)) {
    array[i + 1] = array[i];
    i--;
  }

  // index is stopped one place behind because of the last iteration's
  // decrement, so add 1 and insert value here
  array[i + 1] = value;
}

function insertionSort(array) {
  // Walk forward in the array
  for (var i = 0; i < array.length; i++) {
    // In the best case scenerio, the list is partially sorted. O(n)
    // However when the array is not sort (randomly arranged),
    // it performs in O(n^2), because it has to walk all the way back
    // in most cases during the insertion phase.
    _insert(array, i, array[i]);
  }
}

function insertSortStartBackwards(array) {
  for (var i = array.length - 1; i >= 0; i--) {
    _insert(array, i, array[i]);
  }
}

function recursiveInsertionSort(array, n) {
  if (n === undefined) {
    n = array.length - 1; // Start at the end of the array.
  }

  if (n <= 0) { // Stop the recursion when we reach the end of the array
    return array;
  }
  recursiveInsertionSort(array, n - 1);
  _insert(array, n, array[n]);
}