読み方：きすうソート

基数ソート【radix sort】

概要

基数ソートとは、与えられたデータ列を大小などの順序通りになるよう並べ替えるソート（整列）アルゴリズムの一つで、数値や文字列を構成する各桁の値を下位桁から（または上位桁から）順に処理することで全体を並び替える方式。要素同士を直接比較せずに整列できる非比較型ソートの一つである。

クイックソートなど一般的なソートアルゴリズムでは要素同士の大小比較を繰り返してデータを並び替えるが、基数ソートは各桁の値（0～9など）に基づいてデータをグループに振り分ける操作を桁数分だけ繰り返す。比較操作を行わないため、比較ベースのソートが理論上超えられない O（n log n）の計算量の壁に縛られず、条件が整えば O（n）に近い処理が可能である。

10進数の整数を並べ替える場合、まず1の位の数字だけを見て全データを0～9の10個のバケツに振り分け、バケツの順に並べ直す。次に10の位について同じ操作を行い、さらに100の位、1000の位…と続けていく。この処理を最大桁数分だけ繰り返すと、最終的に全体が昇順に整列される。

各桁での振り分けには、順序を保持するために安定ソートである「カウントソート」（counting sort）が内部処理として使われることが多い。下位桁から処理する方式を「LSD」（Least Significant Digit）型、上位桁から処理する方式を「MSD」（Most Significant Digit）型と呼ぶ。LSD型は固定長のデータに適しており、MSD型は可変長の文字列ソートなどに応用できる。

適用できるデータには強い制約があり、整数や固定長のASCII文字列など、桁構造を持ち、かつ一桁が取り得る内容の選択肢が少ないようなものに限られる。また、桁数や基数に応じたメモリ領域が必要になる。適用場面が限られるため汎用ソートライブラリなどで採用されることは少なく、大量の整数データを高速に整列したい場合など、特定な用途で個別に実装される。