基数ソート
要素間の比較に基づかないソートアルゴリズム
w
bitの整数の整列を
d
bitずつ、
w/d
回行う
計数ソート
を複数回行う
計算量
$ O((w/d)(n+2^d))
配列の要素が
$ \{0,...,n^c-1\}
の範囲の整数、かつ
$ d=[\log{n}]
であれば
$ O(cn)
に整理できる