Prompt
Radix sortが使える条件は？
やっほー！アルゴリズムの旅もいよいよRadix Sort（基数ソート） まで来たね！
比較ベースのソート（Quick Sortとか）が の壁にぶつかる中で、条件さえ揃えば に迫るスピードを出す、まさに「特化型」のアルゴリズムだよね。
でも、その「特化型」ゆえに使える条件は結構シビアなんだ。情報工学徒として、これを使えるかどうかのチェックリストを整理したよ！
1. 必須条件：データが「辞書順」に並べられること
基数ソートが動く大前提は、データを 「複数の桁（あるいはパーツ）」 に分解できて、それぞれの桁に優先順位があることだよ。
-
整数: 1の位、10の位、100の位……と分けられるから最適！
-
文字列: 1文字目、2文字目……と辞書順に並べられるからOK。
-
固定長データ: IPアドレス（4つのオクテット）や、日付（年・月・日）なんかも得意分野だね。
2. 必須条件：各「桁」の値の範囲が限定されていること
基数ソートは内部で Counting Sort（計数ソート） などの安定ソートを各桁に対して呼び出すんだ。
-
10進数なら各桁は
0〜9の10種類。 -
アルファベットなら
a〜zの26種類。この「種類数（基数）」が多すぎると、内部で使うメモリが爆発して、逆に遅くなっちゃうんだよ。
3. ⚠️ 見落とされがちな「落とし穴」
① 負の数や小数が混じると一気に面倒！
「整数ならOK」と言ったけど、実は負の数が混じるとそのままでは動かないんだ。
-
対策: 全データに最小値分のオフセットを足してプラスにするか、符号ビットで分ける処理が必要になるよ。
-
小数: 浮動小数点数（IEEE 754）もビット列として見ればソート可能だけど、指数の扱いが特殊だから、単純な基数ソートのコードではバグる可能性が高いんだ。
② 「安定ソート」である必要がある
内部で各桁をソートするアルゴリズムは、必ず安定（同じ値の順序が入れ替わらない） じゃないといけないんだ。
もし不安定なソート（Quick Sortなど）を内部で使うと、せっかく下の桁で揃えた順番が、上の桁のソートでめちゃくちゃに破壊されちゃうんだよ！
③ メモリ効率（空間計算量）
基数ソートは （ は基数）のメモリを消費するよ。データ量 が膨大で、かつ基数 も大きい場合、メモリ不足に陥るリスクがあるから注意してね。
4. 豆知識：LSD vs MSD
基数ソートには2つの流派があるんだ。
-
LSD (Least Significant Digit): 下の桁（1の位）から順にやる方法。一般的で実装が楽！
-
MSD (Most Significant Digit): 上の桁からやる方法。文字列のソートなどで、頭文字が違う時点で勝負がつく場合に効率的だけど、再帰が必要で複雑だよ。