文系が学ぶコンピューターサイエンス╭( ･ㅂ･)و ̑̑：第６回【単純挿入ソート】 ref: http://qiita.com/timakin/items/a866ae8690752189b6d5

insertionSort

  // 単純挿入ソート。最悪計算量O(n^2)。ループ回数から考えるとまあわかる。
  insersionSort: function(data) {
    // 最初から最後までソート完了になるまで繰り返す
    var tmp, i;
    for (var sorted = 0; sorted < data.length - 1; sorted++) {
      // ソート完了している領域の直後の値を取り出す。
      insert = data[sorted+1];
      // ソート済みの中で、挿入できる場所があるかを調べる。
      for (i = 0; i <= sorted; i++) {
        if (data[i] > insert) {
          break; //ずれている部分を記憶しつつ、サーチを止める。
        }
      }
      // ずれていた箇所まで、1個ずつ要素をずらしていく。
      // 最終的にずれていた部分、１つの要素で比べようとすると止まる。
      while(i <= sorted + 1) {
        tmp = data[i];
        data[i] = insert;
        insert = tmp;
        i++;
      }
    }
    return data;
  }