ラディックスソートとは？仕組み・LSD/MSDの違い・計算量と実装上の注意点

ラディックスソートとは

ラディックスソート（Radix Sort）は、キーを「桁（digit）」ごとに分解して比較・並べ替えを行う非比較型の安定ソートアルゴリズムです。比較ソート（例えばクイックソートやヒープソート）が理論上 O(n log n) の下限を持つのに対し、ラディックスソートはキーの長さや基数に依存する次数で動作し、固定長のキー（整数や固定長文字列など）の場合に非常に高速に動作します。

基本的な考え方

ラディックスソートはキーを「桁」に分解し、桁ごとに安定な並べ替えを行うことを繰り返します。桁の処理順によって主に2種類に分類されます。

• LSD（Least Significant Digit）方式：最下位桁から最上位桁へ順に処理します。各桁で安定なソート（通常は基数ごとにカウントするカウントソート）を使うことで最終的に全体が正しくソートされます。固定長の整数や固定長文字列に向く簡潔な方式です。
• MSD（Most Significant Digit）方式：最上位桁から下へ分割（再帰）していきます。各桁でキーをバケットに分配し、バケットごとにさらに次の桁で分配することで最終的にソートされた列を得ます。可変長文字列や先頭の桁で早期に分散するデータに有利です。

内部で使われる手法：カウントソート

各桁の処理に用いられる代表的な安定ソートはカウントソートです。カウントソートは「基数（radix）」を b とすると、O(n + b) の時間でその桁に基づく安定な分配を行えます。ラディックスート全体の時間は桁数 k を用いて O(k*(n + b))、典型的には O(k n + k b) と表現されます。基数 b は一般的に扱う桁の表現で、例えばバイト単位なら b = 256、2進ビット群で処理するなら b = 2^r となります。

計算量と空間計算量

• 時間計算量：典型的に O(k (n + b))。ここで n は要素数、k はキーあたりの桁数（またはパス数）、b は基数（バケット数）。ビット幅 w の整数を r ビットずつ処理する場合、k = ceil(w / r) として O((w/r) * (n + 2^r)) と表せます。
• 空間計算量：通常 O(n + b)。安定な分配のために出力配列やカウント配列が必要になるためです。in-place版（American Flag Sort など）も存在しますが実装が複雑です。
• 比較ソート下限の回避：固定長のキーに対しては比較ベースの下限 O(n log n) を超えてより良い性能を出せます。これは比較演算のみを用いるモデルの下限に依存しているため、キーの構造（桁）を利用するラディックスソートは別モデルとなるためです。

LSD と MSD の違いと利用場面

LSD は実装が単純で、特に固定長の整数や固定長のキーに対して非常に効率的です。パスごとに配列全体を走査するためメモリアクセスは規則的でキャッシュフレンドリーなことが多いです。一方 MSD は可変長文字列のソートや、先頭の桁で大きく分布が分かれる場合に有利で、再帰的にバケツを処理するため一部のデータで早く終了することがあります。

負の数・浮動小数点・可変長文字列の扱い

• 負の整数：二の補数表現を利用している場合、単純に符号ビットを含めたビット列をそのまま扱うと符号順と一致しないことがあります。整列のためには「符号ビットを反転する」か、最上位ビット（符号）をオフセットとして扱うことで unsigned としての順序に変換する手法（バイアスを掛ける、あるいは高位ビットを反転）を用います。
• 浮動小数点（IEEE 754）：ビット表現を用いる場合、正負で並びが入れ替わる問題があります。一般的なテクニックは、正の値は上位ビットのまま、負の値はビットを反転して unsigned にした上でラディックスートを行い、最終的に元に戻す方法です（符号と指数部の扱いに注意）。
• 可変長文字列：MSD を使うのが自然です。終端（終端文字）を考慮し、短い文字列が先に来る順序を確保するために「桁がない」状態を最小値として扱うか、別カウントを用意します。バーストソート（burstsort）やトライ構造を組み合わせた高速実装も存在します。

実装上の注意点と最適化

• 基数 b の選択：大きすぎるとカウント配列や初期化コストが増え、小さすぎるとパス数が多くなります。例えば32ビット整数なら r=8（b=256）で4パス、r=11（b=2048）で3パスにできるが、b が大きいほどカウント配列の初期化とメモリ使用が問題になる。
• 安定性の確保：LSD では各パスにおいて必ず安定な並べ替え（カウントソートなど）を用いること。MSD ではバケット内で安定性を考慮するか再帰的に処理する必要がある。
• メモリアクセスの局所性：出力配列へ連続して書き込む設計や、カウント配列を先に走査してオフセットを事前計算する手法（プレフィックス和）でキャッシュ効率が向上します。
• 分配回数の削減：パス毎に単純に全要素をコピーするのではなく、各バケットごとの要素をまとめてコピーする・インプレース分割を行う（American Flag Sort）などでメモリ操作を減らすことが可能です。
• 並列化：各パスのバケット分配は並列化がしやすく、GPU やマルチコア CPU 上での高速化研究が盛んです。並列ラディックスートは、ローカルカウントをとってから全体のオフセットを計算して分配する手法が一般的です。

代表的な派生・関連アルゴリズム

• カウントソート（Counting Sort） - ラディックスートの内部で多用される安定ソート。
• アメリカンフラグソート（American Flag Sort） - MSD の in-place 版に相当し、メモリコピーを最小にする実装。
• ラディックスチェンジソート（Radix Exchange Sort） - ビットの分割を利用したクイックソート風の再帰的ビット分割法。
• バーストソート（Burstsort） - 可変長文字列を扱う際の高速な実装のひとつ。

実際の選択基準・利用場面

ラディックスートは次のような場面で非常に有用です。

• 大量の固定長キー（例えば32bit/64bit整数）のソート：比較ソートより高性能。
• 短い文字列（電話番号、ID、ハッシュ値等）のソート。
• 外部ソートや大規模データでパス数・I/O 回数を明確に制御したい場合（基数分配は外部メモリに向いた戦略を取りやすい）。

一方で、キーが可変長かつ非常に長い文字列群でかつ先頭での差が少ない場合や、一般的な用途でのライブラリ利用（std::sort 等）では比較ソートの方が単純かつメモリ節約的に有利な場合もあります。

実装例（疑似コードイメージ）

ここでは簡略化したLSD方式の疑似コードのイメージを示します（キーをバイト列と仮定、基数256）。

• for d = 0 to k-1 (最下位バイトから)
  • カウント配列 count[0..255] をゼロ初期化
  • 全要素についてそのバイト値をインクリメントしてカウント
  • count をプレフィックス和にして各バケットの開始オフセットを計算
  • 元配列を走査し、安定に出力配列へ配置
  • 元配列 <- 出力配列（次のパスに備える）

よくある誤解と注意点

• 「ラディックスートは常に速い」：固定長キーでは有利ですが、基数の選択・メモリ使用・キャッシュ効率により性能は変動します。
• 「負の数・浮動小数点はそのまま使える」：ビット表現ままでは順序が崩れるため、前処理（ビット反転やバイアス付加）が必要です。
• 「比較ソートの下限を破る」：ラディックスートは比較以外の情報（桁）を利用するため比較ベースの下限に依存しないという意味であり、モデルが異なることに注意。

まとめ

ラディックスソートは、桁ごとの安定な分配を繰り返すことで高速な整列を実現するアルゴリズムで、特に固定長の整数や短い文字列の大量ソートで威力を発揮します。LSD と MSD、それぞれに適した用途とトレードオフ（メモリ使用、パス数、局所性など）があり、基数の選択や安定性の担保、負の数や浮動小数点の取り扱いといった実装上の注意点を押さえることが重要です。用途に応じてカウントソート等の下請けアルゴリズムや in-place、並列化、外部メモリ対応の工夫を組み合わせることで、実運用での性能を最大化できます。

参考文献

• Wikipedia: ラディックスソート（日本語）
• Wikipedia: Radix sort (English)
• CLRS（Cormen et al.） — Chapter on Sorting (参考教材)
• Princeton: Radix Sort（Sedgewick 講義資料）
• CP-Algorithms: Radix Sort（実装と注意点）
• Wikipedia: American flag sort