插入排序，初始状态第一个元素为已排序序列，以此取出后面无序区元素与有序区进行从后往前比较，以找到在有序区的位置。Insert Sort, initial first element is an ordered subset, traverse remain elements and find correct location for every element from unordered subset.

insertSort.js

/**
 * 插入排序，时间复杂度最坏O(n^2)，最好（基本有序）O(n)；空间复杂度O(1)
 * @param {Array} arr 需要进行排序的数据源
 * @return {Array} arr 排序完成后的数组
 */
function insertSort(arr) {
  var len = arr.length;
  for(var i=1; i<len; i++) {
    var sortedIndex = i - 1;
    var unSortedData = arr[i];
    while(sortedIndex >= 0 && unSortedData < arr[sortedIndex]) {
      arr[sortedIndex + 1] = arr[sortedIndex];
      sortedIndex -= 1;
    }
    arr[sortedIndex + 1] = unSortedData;
  }
  return arr;
}