挿入ソート(insertion sort)

先頭から整列していき、整列部後方から挿入値を順次比較して適切な位置に挿入する。挿入と言いつつ、動きは交換交換の荒らしなんだよなぁ。結果的には挿入したように見えるんだけど。ちなみに自分で書けなくて Wikipedia を参考にした orz

def insertion_sort(list)
  dup = list.dup
  1.upto(dup.length - 1) {|i|
    tmp = dup[i]
    j = 0
    i.downto(0) {|j|
      break if dup[j - 1] <= tmp
      dup[j] = dup[j - 1]
    }
    dup[j] = tmp
  }
  dup
end