バケツソートとn log nの壁 - アルゴリズムクイックリファレンス４章の補足 - ref: http://qiita.com/sasanquaneuf/items/39d00e6f49d87643d472

bucket

def bsort(a) # 非破壊的
  l = a.length
  b = Array.new(l){0}
  for i in 0..(l-1) do
    b[a[i]] = a[i]
  end
  return b
end

compare

# 乱数列の作成
timearr.push Time.now.instance_eval { self.to_i * 1000000 + usec}
N = 100000
target = Array.new(N){0}
n = -1
temp = Array.new(N){n;n+=1}
n += 1
while n > 0 do
  t = rand(n)
  n -= 1
  target[n] = temp[t]
  temp.delete_at(t)
end

targeta = target.clone
targetb = target.clone

timearr.push Time.now.instance_eval { self.to_i * 1000000 + usec}
bsort(targeta)
timearr.push Time.now.instance_eval { self.to_i * 1000000 + usec}
msort(targetb)
timearr.push Time.now.instance_eval { self.to_i * 1000000 + usec}

p timearr[1] - timearr[0]
p timearr[2] - timearr[1]
p timearr[3] - timearr[2]

結果

773380  # 準備の時間
14539   # バケツソート（無重複）の時間
253719  # マージソートの時間