線形時間ソート

とりうる値が既知のK通りである時O(N+K)

直感的な実装: K個のリストを用意しておいて出現したものをそこに入れていく

特殊ケースとしてN通りである時、それぞれ1回しか出現しないのでサイズNの配列を用意すれば良い、O(N)

ソート対象の値だけをソートする時の実装方法の一つ

各値の出現回数を数える

中身が同一な可変長リストを実際にメモリにもたなくても「値がiのものがni個ある」とわかれば十分なので

objをobj.xによってソートするような場合はobj.xが同一でもobjは同一ではないのでこの方法はできない

値が一定の範囲外なら無視して良いケース

0以上の値のソートでMをこえてたらMとみなして良い、など

桁にわかれてる値に対して下位の桁からソートをする

桁数をkとしてO(kN)

各桁に出現しうる値をdとした時にd^kがある程度小さければ(10^6くらい)バケットソートでよい

値の範囲があまり大きいと(Nくらい)、桁数kがlogNで結局O(NlogN)になってしまう

ほとんど整列されてるデータに対してO(N)