基数ソート

基数ソート（きすうソート、英: radix sort）は、「比較によらないソート」のアルゴリズムの一つで、位取り記数法で表現可能な対象について、下の桁から順番にソートしてゆき、最後に最上位桁でソートすると、全体が順序通りに並ぶ、という手法である。 nをデータの数、kを桁数として、計算量のオーダーはO(nk)である。また、アルゴリズム自身の性質により、素直な実装が安定ソートになる。