単純挿入ソート

2番目の要素から先頭に向かって適当な位置に挿入をしていく。
計算量はO(n^2)。
最良時はそれぞれの要素が適当な位置に収まっていることを確認するためのO(n)。
ソート済みの部分が多いときは高速だが、要素を１つずらすコストが高い。
したがって、ランダムな要素については性能が出ないが、
ソート済み要素に対する性能が高く、かつ安定的という性質を持つ。
（要素をずらすコストについては、ライブラリに配列をずらす関数が用意されている場合、
コンパイラによる最適化が働く（ポインタ使用）場合で性能が向上する。）

このアルゴリズムの発展系がシェルソートとなる。

#挿入のため要素を１つずらすコストが高い
#大まかにシャトルソートを行うことで交換回数を減らすのがシェルソートになる

def shuttlesort!(array)
  1.step(array.size - 1, 1) do |i|
    target = array[i]
    insertion = nil;
    i.step(0, -1) do |j|
      insertion = j
      if array[j - 1] < target then
        break
      end
      array[j] = array[j - 1]
    end
    array[insertion] = target
  end
end

data = Array.new
while input = $stdin.gets.to_i
  break if input < 0
  data << input
end

p data
shuttlesort!(data)
p data