基数ソート（きすうソート、）は、ソートのアルゴリズムの一つ。計算時間はO(nk)と高速で、かつ安定ソートであるが、O(n)の外部記憶（高速なメモリーでなくてもよい）が必要。（ここで、nはデータの数、kはキーの桁数を意味する。）基数ソートのアルゴリズムは、データの種類が有限で、最大値・最小値がはっきりしていることを仮定している。すべての入力データが「3桁の整数」や「2文字のアルファベット」など決まった形式であることが分かっているときに適用できる。(1)入力の数列は、いくつかのキーに分類する。例えば、3桁の数字であれば、1の位・10の位・100の位に分けて分類する。(2)それぞれのキーについて、下位のキーからソートする。この際、値の範囲が有限であることからバケットソートが効率的である。（ここで、O(n)でないソートアルゴリズムを用いると、全体の計算時間が O(nk)でなくなることに注意。また、安定なソートでなければならない。）たとえば、という数列を1の位についてソートすると、となる。さらに、10の位についてソートすると、となる。最後に、100の位についてソートすると、となり、ソートが完了する。コンピュータの数値の内部表現は、通常4バイトや8バイトのビット列となっている。これら4バイト（8バイト）の整数については、1バイトずつ（あるは4ビットずつ）のキーに分類して基数ソートを適用することが可能である。ただし、通常、最上位部に「符号ビット」を持つため、これに関して特別な扱いをする必要がある。浮動小数点形式の数値については、などの方策をとることができる。コンピュータ以外での応用に、周辺部に穴の開いた紙カードの、穴から外側の部分の紙を情報に応じて切り欠いたもの（パンチカード#ハンドソート・パンチカード・システム）のソート方法というものがある。穴の場所に串を通し持ち上げると、その穴のところを切り欠いたカードが残り、切り欠いてないカードが選び出される。そうして選び出したカードを片側に寄せる。二進法の下の桁からこの操作を繰り返すと、基数ソートになる。

出典:wikipedia