バケツソートをRubyで

バケツソート、これは内部で使っている挿入ソート部分以外で比較をしないソート。
なんかwikipediaのバケツソートのページを見ると、計数ソートと同じだとか、計数ソートのコードや図が乗っているという無茶苦茶な状態なので、英語版のwikipediaを参照したい。
計数ソートとは別のアルゴリズムです。

バケツソートでは、ある一定の方法で要素をバケツ（グループ）に分けて、そのバケツ毎に挿入ソートでソートしてからバケツを連結する。
この「ある一定の方法」というのは入力の制約に大きく依存するので、以下の実装では、入力を「２桁以下の数」であることを仮定して、バケツの添字には「２桁目の数字」を使用する。
たとえば、23 は 2 のバケツに入るし、55は 5 のバケツに入る。 1 は 0 のバケツに入る。

class Array
  def insertion_sort!
    1.upto(size-1) do |i|
      key = self[i]
      j = i - 1
      while j >= 0 && self[j] > key
        self[j+1] = self[j]
        j -= 1
      end

      self[j+1] = key
    end
  end

  def bucket_sort
    buckets = Array.new(10) { [] }

    each { |n| buckets[n / 10] << n }

    buckets.each(&:insertion_sort!).reduce(:+)
  end
end

a = [45,39,32,72,1,91,56,3]
p a.bucket_sort

[1, 3, 32, 39, 45, 56, 72, 91]

要素を比較することなく、ある程度バケツ分けできる方法と、要素が少なかったりソート済みの場合に有効な挿入ソートを組み合わせる手法だ。