LSD法（基数ソート・下位桁優先）完全ガイド：仕組み・実装・計算量・注意点
エバープレイ編集部LSD法とは — 基数ソートの「下位桁優先」アプローチ
LSD法（Least Significant Digit 法）は、基数ソート（Radix Sort）の一種で、キーの「下位桁（最も重要度の低い桁）から上位桁へ順に処理していく」ソート手法を指します。整数や固定長文字列のソートでよく用いられ、比較に基づくソート（クイックソート、マージソートなど）とは異なり、キーの桁ごとに安定なソート（通常は計数ソート）を繰り返して最終的な全体の順序を得ます。特徴として「安定性を利用すること」「桁数に比例した線形時間的振る舞いを示すこと（条件付き）」が挙げられます。
基本原理（なぜ下位桁からできるのか）
LSD法の核心は「各桁ごとのソートを安定に行えば、下位桁→次に上位という順で処理することで最終的に全体が正しくソートされる」という性質です。例として3桁の数値を考えると、まず最下位桁で安定ソートを行うと、同じ下位桁を持つ要素の相対順は維持されます。次に十の位で安定ソートすると、十の位の順序が確定する一方で、同じ十の位内では直前の下位桁ソートで確立した順序（＝下位桁の順序）が残るため、最終的に全桁を適切に処理した段階で正しい全体順序が完成します。
アルゴリズムの流れ（典型的な実装）
代表的な実装手順は以下のとおりです。ここでは基数（radix）を b（例：10進なら10、バイト単位なら256）とし、キーを k 桁とする場合を想定します。
- 入力配列 A を用意する。
- 最下位桁（d = 0）から始めて、d = 0..k-1 の順で以下を繰り返す。
- 各要素の d 桁目を抽出し、桁値をキーとして「安定な」ソート（典型的には計数ソート）を用いて配列を並べ替える。
- 最後の桁処理が終われば、配列は完全にソートされている。
簡単な擬似コード：
for d in 0..k-1:
stable_sort_by_digit(A, d, base=b)ここで stable_sort_by_digit はキーの d 桁目を基準に安定なソートを行う関数（通常は O(n + b) の計数ソート）です。
安定性（Stability）が不可欠な理由
各桁のソートが「安定」でなければ、既に確定したより下位桁の順序が失われ、正しい最終順序を得られません。したがって、LSD法では各桁の処理に安定ソートを用いることが必須です。実装上は計数ソート（Counting Sort）が最もよく使われます。計数ソートはキーの取り得る範囲（基数 b）に対して線形時間で動作し、安定性を保てるためです。
計算量・メモリ使用量（理論的評価）
- 時間計算量（一般形）: O(k * (n + b)) — n は要素数、k は桁数、b は基数（digit range）
- 基数 b が定数（例：10 や 256）で、k を定数あるいは log_{b} M（M はキーの最大値）と見なすと、時間は O(n * k) あるいは O(n) に近い線形時間を示す。
- 空間計算量: O(n + b)（出力配列およびカウント配列を用いる場合）
注意点として、b を大きく取れば k は小さくなりますが、計数配列のサイズが b に比例して増えるのでメモリ・初期化コストが上がります。逆に b を小さくするとパス数 k が増えます。実際の実装ではバランスを取る（例：バイト単位で r=8 bit ごとに処理して radix=256 とする等）ことが重要です。
整数・負数・符号付き値の扱い
LSD法で整数を扱う場合、非負整数は自然に処理できます。符号付き整数（負数を含む）を扱う場合は注意が必要です。単純に2の補数表現のバイト列をそのままLSDで処理すると、符号の影響で正しい順序にならないことがあるため、以下の対処が一般的です。
- 符号ビットを考慮してオフセットを取る（例：全要素に定数を足して非負に変換してからソートし、最後に戻す）。
- 最上位ビット（符号ビット）を特別扱いするか、最終段階で負と正を結合する。
- 2の補数表現をバイト列として扱う場合は、最上位バイトの符号を反転するなどの変換で順序を得るテクニックもある。
可変長文字列の扱い（注意点と方法）
LSD法は固定長キーに非常に向きますが、可変長文字列（長さが異なる文字列）をそのまま下位桁から処理するのは難しいことがあります。典型的な対処法は以下の通りです。
- 短い文字列をパディングする（末尾に特殊な最小値文字を入れるなど）。ただし元の順序や辞書順と一致させるために慎重な設計が必要。
- 可変長に対応したバージョンでは、短いキーの「桁が存在しない」ことを考慮して安定に扱う手法を導入する（例：存在しない桁を最小値、もしくは特定のセパレータとして扱う）。
- 一般には可変長文字列には MSD（Most Significant Digit、上位桁優先）法の方が向いていることが多い（共通接頭辞を活かせるため、平均的に効率が良い場合がある）。
LSDとMSDの比較・使い分け
基数ソートにはLSD（下位桁優先）とMSD（上位桁優先）の2つの主要なアプローチがあります。使い分けのポイントは次のとおりです。
- 固定長キー（例えば同じ長さの整数やゼロ埋めした文字列）: LSDが実装容易で安定。メモリとパス数のバランス次第で高速。
- 可変長キー（長さにばらつきがある文字列）: MSDが有利な場合が多い。共通接頭辞を利用して局所的に分割できるので不要な桁処理を減らせる。
- メモリ制約が厳しく、インプレースでの振る舞いが要求される場合: LSDは通常バッファを必要とするため注意が必要（インプレース化は複雑）。
- 安定性が重要なケース（例えば複数キーの多段ソート）: LSDは自然に安定な段階的ソートと親和性がある。
実装上の最適化・実用的なポイント
- 基数選択: バイト単位（radix=256）は一般的。64ビット整数なら8バイト分を1パスで扱うか、2バイトずつに分けるかはメモリとパフォーマンスのトレードオフ。
- キャッシュ効率: 大きな基数だとカウント配列の初期化やキャッシュミスが増える。適切な基数でキャッシュに合う処理を心がける。
- 並列化: 各パスのカウント段階は並列化しやすいが、パス自体は上位桁に進むまで次のパスへ進めないためシーケンシャルな部分も残る。GPUやSIMDでバケット集計を高速化する実装例がある。
- 外部メモリ: 大量データを外部ソートする場合、パス数やシークの回数を減らす工夫（大きめの基数やブロック処理）が必要。
- 負荷分布: キーの分布が偏っていると特定バケットに偏り、性能が落ちる。必要に応じて前処理で分割やサンプリングを行う。
いつLSD法を使うべきか（適用例）
- 大量の固定長整数（IDS、タイムスタンプなど）のソート。キーが同一長であれば高速に動作する。
- 固定長のバイナリキー（IPv4アドレス、ハッシュ値の先頭部など）の並べ替え。
- 複数キーでの多段ソート（下位キー→上位キーの順にLSD的に処理）により、安定ソートを活かした実装。
- ハードリアルタイム要件や決定論的時間に近い性能が欲しい場面（比較ベースの最悪 O(n log n) よりも一定条件下でより安定した振る舞いを期待できる）。
欠点・注意点（選択時のリスク）
- キー長が大きい・可変長の場合、パス数が増えるためコストが上がりやすい。
- 基数 b が大きいとメモリ使用量と初期化コストが増大する。
- 汎用的な比較ベースソート（例：イントロソート）と比べると実装の複雑さやケース依存のチューニングが必要。
- 負数・符号付きデータ・可変長データの扱いを間違えると誤ソートにつながる。
実際の例（簡単なワークフロー）
例：10進数の3桁の数列 [329, 457, 657, 839, 436, 720, 355] を LSD 法でソートする流れの概略：
- 1回目（1の位で安定ソート） → 下位の順序を確定。
- 2回目（10の位で安定ソート） → 10の位の順序が確定。10の位が同じグループ内では1の位の順序が保たれる。
- 3回目（100の位で安定ソート） → 全桁が確定し最終ソート完了。
まとめ
LSD法は「下位桁から上位桁へ」順に安定ソートを繰り返すことで全体を整列する基数ソートの一種です。固定長のキーや大量データを扱う場面で、適切に基数と実装を選べば比較ソートより高速に動作することが多く、特に安定性を活かした多段ソートに適しています。一方で可変長キーや符号付きデータ、メモリ制約が厳しい状況では注意が必要で、MSD法や比較ベースのソートの方が適する場合もあります。実装では基数の選択、計数ソートの安定実装、メモリとキャッシュ効率を考慮することが重要です。
参考文献
- 基数ソート - Wikipedia（日本語）
- Radix sort - Wikipedia (English)
- Algorithms, 4th Edition（Sedgewick & Wayne） — Princeton Algorithms（解説に基数ソートの記述あり）
- Open Data Structures — Radix sort の解説
- CS StackExchange: How does LSD radix sort work?（Q&Aで具体例）
- GeeksforGeeks — Radix Sort（実装例と解説）
投稿者プロフィール
