dictionary云々はハッシュ関数で非可逆圧縮してからバケットソートするようなもの
バケットソートはO(n)