基数ソートは、ソートのアルゴリズムの一つ。計算時間はO(nk)と高速で、かつ安定ソートであるが、O(n)の外部記憶（高速なメモリーでなくてもよい）が必要。（ここで、nはデータの数、kはキーの桁数を意味する。）

(1)入力の数列は、いくつかのキーに分類する。例えば、3桁の数字であれば、1の位・10の位・100の位に分けて分類する。
(2)それぞれのキーについて、下位のキーからソートする。この際、値の範囲が有限であることからバケットソートが効率的である。（ここで、O(n)でないソートアルゴリズムを用いると、全体の計算時間が O(nk)でなくなることに注意。また、安定なソートでなければならない。）

たとえば、
170, 45, 75, 90, 2, 24, 802, 66

という数列を1の位についてソートすると、
170, 90, 2, 802, 24, 45, 75, 66

となる。さらに、10の位についてソートすると、
2, 802, 24, 45, 66, 170, 75, 90

となる。最後に、100の位についてソートすると、
2, 24, 45, 66, 75, 90, 170, 802

となり、ソートが完了する。