整数ソート

コンピュータサイエンスにおいて、整数ソートは、整数キーによってデータ値のコレクションをソートするアルゴリズムの問題です。整数ソート用に設計されたアルゴリズムは、キーが浮動小数点数、有理数、またはテキスト文字列であるソート問題にも適用されることがよくあります。^[1]キーに対して整数演算を実行できるため、多くの場合、整数ソートアルゴリズムは比較ソートアルゴリズムよりも高速になりますが、これはコンピューティングモデルで許可されている操作の詳細と、ソートする整数の大きさによって異なります。

ピジョンホールソート、カウンティングソート、基数ソートなどの整数ソートアルゴリズムは広く使用されており、実用的です。最悪の場合の時間制限がより小さいその他の整数ソートアルゴリズムは、ワードあたり 64 ビット以下のコンピュータアーキテクチャでは実用的ではないと考えられています。このようなアルゴリズムは多数知られており、パフォーマンスはソートする項目の数、キーあたりのビット数、ソートアルゴリズムを実行するコンピュータのワードあたりのビット数の組み合わせによって異なります。

一般的な考慮事項

計算モデル

整数ソートアルゴリズムの時間制限は、通常、ソートするデータ値の数 $n$ 、ソートするキーの最大可能値 $K$ 、アルゴリズムを実行するコンピュータの 1 つのマシンワードで表現できるビット数 $wの 3 つのパラメータによって決まります。通常、$ $w \geq log 2 (max(n, K))$ と想定されます。つまり、マシンワードは、入力データのシーケンスのインデックスを表すのに十分な大きさであり、単一のキーを表すのに十分な大きさでもあります。^[2]

整数ソートアルゴリズムは、通常、ポインタマシンまたはランダムアクセスマシンのコンピューティングモデルで動作するように設計されている。これら 2 つのモデルの主な違いは、メモリのアドレス指定方法である。ランダムアクセスマシンでは、レジスタに格納されている任意の値を、操作ごとに単位コストでメモリの読み取りおよび書き込み操作のアドレスとして使用できる。この機能により、テーブル参照を使用して、データに対する特定の複雑な操作を迅速に実装できる。対照的に、ポインタマシンモデルでは、読み取りおよび書き込み操作でポインタに格納されているアドレスが使用され、これらのポインタに対して算術演算を実行することは許可されていない。どちらのモデルでも、データ値は追加でき、ビット単位のブール演算とバイナリシフト演算も通常、操作ごとに単位時間で実行できる。ただし、異なる整数ソートアルゴリズムでは、整数乗算も単位時間操作として許可されるかどうかについて異なる仮定が立てられている。^[3]並列ランダムアクセスマシンなどの他のより特殊な計算モデルも検討されている。^[4]

Andersson、Miltersen、Thorup (1999) は、一部の整数ソートアルゴリズムで必要な乗算やテーブル参照を、ハードウェアで簡単に実装できるが、汎用コンピュータでは通常利用できないカスタマイズされた操作に置き換えることができる場合があることを示しました。Thorup (2003) は、これらの特別な操作をPentiumプロセッサで既に利用可能なビットフィールド操作命令に置き換える方法を示して、これを改善しました。

コンピューティングの外部メモリモデルでは、比較ソートよりも高速な整数ソートアルゴリズムは知られていない。研究者らは、これらのモデルでは、キーの操作方法が制限されているアルゴリズムの制限されたクラスは比較ソートよりも高速にはならないこと、^[5]および比較ソートよりも高速な整数ソートアルゴリズムは、ネットワークコーディングにおける標準的な推測が間違っていることを意味することを示した。^[6]

ソートと整数優先キュー

優先キューは、数値の優先順位を持つアイテムのコレクションを維持するためのデータ構造であり、最小の優先順位値を持つアイテムを検索して削除する操作を実行します。バイナリヒープなどの比較ベースの優先キューは、更新ごとに対数時間がかかりますが、ファンエムデボアズツリーやバケットキューなどの他の構造は、優先順位が小さな整数である入力に対して高速になる場合があります。これらのデータ構造は、選択ソートアルゴリズムで使用できます。選択ソートアルゴリズムは、コレクションから最小の要素を繰り返し検索して削除し、見つかった順序で要素を返すことで、要素のコレクションをソートします。優先キューは、このアルゴリズムで要素のコレクションを維持するために使用できます。n 要素のコレクションに対するこのアルゴリズムの時間は、 $優先キューを初期化してから$ $n 回$ の検索および削除操作を実行する時間によって制限されます。たとえば、選択ソートでバイナリヒープを優先キューとして使用すると、ヒープソートアルゴリズム、つまり $O (n log n)$ 時間がかかる比較ソートアルゴリズムになります。代わりに、バケットキューで選択ソートを使用すると、ピジョンホールソートの一種が得られ、ファン・エムデ・ボアズ木やその他の整数優先キューを使用すると、他の高速整数ソートアルゴリズムが得られます。^[7]

ソートアルゴリズムで整数優先キューを使用する代わりに、逆の方向に進み、整数ソートアルゴリズムを整数優先キューデータ構造内のサブルーチンとして使用することも可能です。Thorup (2007) はこのアイデアを使用して、キーごとに $T (n)$ の時間で整数ソートを実行できる場合、優先キューデータ構造での挿入または削除操作ごとの時間にも同じ時間制限が適用されることを示しました。Thorup の簡約は複雑で、高速な乗算操作またはテーブル参照のいずれかが利用可能であることを前提としていますが、彼はまた、操作ごとに $T (n) + T (log n) + T (log log n) + ...$ の時間で、最大で反復対数を乗算する、加算とブール演算のみを使用する代替の優先キューも提供しています。^[7]

ユーザビリティ

ピジョンホールソート、カウンティングソート、基数ソートといった古典的な整数ソートアルゴリズムは広く使われており、実用的である。^[8]その後の整数ソートアルゴリズムに関する研究の多くは、実用性よりも、最悪のケースの分析における理論的な改善に重点が置かれており、この研究から生まれたアルゴリズムは、現在の64 ビットコンピュータアーキテクチャでは実用的ではないと考えられているが、実験では、これらの方法のいくつかは、キーあたり 128 ビット以上のデータに対して基数ソートを改善する可能性があることが示されている。^[9]さらに、大規模なデータセットの場合、多くの整数ソートアルゴリズムのほぼランダムなメモリアクセスパターンは、メモリ階層を考慮して設計された比較ソートアルゴリズムと比較して不利になる可能性がある。^[10]

整数ソートは、DARPA 高生産性コンピューティングシステムの離散数学ベンチマークスイートの6つのベンチマークのうちの1つであり、 ^[11]NAS並列ベンチマークスイートの11のベンチマークのうちの1つです。

実用的なアルゴリズム

ピジョンホールソートとカウンティングソートはどちらも、 $0から$ $K$ $- 1$ までの範囲のキーを持つ $n個のデータ項目を$ $O$ $($ $n$ $+$ $K$ $)$ の時間でソートできます。ピジョンホールソート(バケットソートとも呼ばれる) では、データ項目へのポインターがバケットのテーブルに配布されます。バケットは、リンクリストなどのコレクションデータ型として表され、キーがテーブルへのインデックスとして使用されます。次に、すべてのバケットが連結されて出力リストが形成されます。^[12]カウンティングソートでは、バケットテーブルの代わりにカウンターテーブルを使用して、各キーを持つ項目の数を決定します。次に、プレフィックス合計計算を使用して、ソートされた出力内で各キーを持つ値が配置される位置の範囲を決定します。最後に、入力に対する 2 回目のパスで、各項目が出力配列内のキーの位置に移動されます。^[13]どちらのアルゴリズムも、入力データ（所要時間 $O$ $($ $n$ $)$ ）と可能なキーのセット（所要時間 $O$ $($ $K$ $)$ ）に対する単純なループのみを含み、全体の所要時間は $O$ $($ $n$ $+$ $K$ $)$ に制限されます。

基数ソートは、データに対して複数回のパスを実行することにより、ピジョンホールソートやカウンティングソートよりも大きなキーに対して機能するソートアルゴリズムです。各パスでは、小さなキーにのみ適した別のソートアルゴリズム (ピジョンホールソートやカウンティングソートなど) を使用して、キーの一部のみを使用して入力をソートします。キーを部分に分割するために、基数ソートアルゴリズムは、選択された基数に従って各キーの位置表記を計算します。次に、アルゴリズムの $i$ 番目のパスに使用されるキーの部分は、最下位桁から最上位桁まで進む、完全なキーの位置表記の $i番目の桁になります。このアルゴリズムが正しく機能するには、データの各パスで使用されるソートアルゴリズムが$ 安定している必要があります。つまり、同じ桁の項目は互いに位置が変わっていてはなりません。効率を最大にするには、基数をデータ項目の数 $n$ に近い値に選択する必要があります。さらに、 $n$ に近い2の累乗を基数として使用すると、高速なバイナリシフトとマスク演算のみを使用して各パスのキーを迅速に計算できます。これらの選択と、ピジョンホールソートまたはカウンティングソートを基本アルゴリズムとして使用すると、基数ソートアルゴリズムは、 $0$ から $K$ $-1の範囲のキーを持つ$ $n$ 個のデータ項目を $O$ $（$ $n$ $log$ $n$ $K$ $）$ の時間でソートできます。^[14]

理論的なアルゴリズム

多くの整数ソートアルゴリズムが開発されており、その理論分析では、ソートする項目の数、キーの範囲、マシンワードサイズを定義するパラメータの組み合わせが十分に大きい場合、比較ソート、ピジョンホールソート、または基数ソートよりも優れた動作をすることが示されています。どのアルゴリズムが最高のパフォーマンスを発揮するかは、これらのパラメータの値によって異なります。ただし、理論的な利点にもかかわらず、これらのアルゴリズムは、実際のソート問題で発生するこれらのパラメータの典型的な範囲では改善されていません。^[9]

小さな鍵のためのアルゴリズム

ファン・エムデ・ボアス木は、それぞれ $0から$ $K$ $- 1$ までの範囲の $n$ 個のキーのセットを $O$ $($ $n$ $log log$ $K$ $)$ の時間でソートするための優先キューとして使用できます。これは、 $K$ が十分に大きい場合に基数ソートよりも理論的に改善されます。ただし、ファン・エムデ・ボアス木を使用するには、 $K$ ワードの直接アドレス指定可能なメモリが必要になるか、ハッシュテーブルを使用してシミュレートする必要があります。これにより、空間は線形に削減されますが、アルゴリズムはランダム化されます。同様のパフォーマンスを持つ別の優先キュー (ハッシュテーブル形式でのランダム化の必要性を含む) は、Willard (1983) の Y 高速トライです。

同様の特徴を持ち、理論的なパフォーマンスが優れている、より洗練された手法が、Kirkpatrick と Reisch (1984) によって開発されました。彼らは、基数ソートの各パスは、最大キーサイズを線形時間で $n$ 倍に縮小する範囲縮小手法として解釈できることを観察しました。代わりに、彼らの手法では、キーサイズを以前の値の平方根 (キーを表すために必要なビット数を半分にする) に縮小し、これも線形時間で行います。基数ソートの場合と同様に、彼らはキーを、およそ $\sqrt$ $K$ である基数 $bの 2 桁の基数$ $b の$ 数値として解釈します。次に、大規模だが初期化されていない直接アドレス指定メモリまたはハッシュテーブルを使用して、線形時間で、ソートする項目をその上位桁に従ってバケットにグループ化します。各バケットには、バケット内で最大のキーを持つ項目である代表値があります。次に、代表値の上位桁と代表値でない下位桁をキーとして使用して項目のリストをソートします。このリストの項目を再度バケットにグループ化することで、各バケットをソート順に配置でき、ソートされたリストから代表値を抽出することで、バケットをソート順に連結できます。このように、線形時間では、ソート問題は、キーが以前の大きさの平方根にはるかに小さい別の再帰ソート問題に縮小されます。キーがバケットソートに十分小さくなるまでこの範囲の縮小を繰り返すと、実行時間 $O($ $n$ $log log$ $n$ $K$ $)$ のアルゴリズムが得られます。

計算のワードRAM モデルにおけるHan & Thorup（2002）の複雑なランダム化アルゴリズムにより、 $これら$ $の$ $時間制限をO($ $n\sqrtloglogK)$ $まで$ $さらに$ 短縮することができます。

大きな単語のためのアルゴリズム

整数ソートアルゴリズムは、log max(n,K)よりも大幅に大きいワードサイズwを必要とする場合、非保守的であると言われる $。$ $[$ $15$ $]$ $極端$ $な$ 例として $、$ w≥Kで^、すべて $の$ $キー$ が異なる場合、キーのセットは、 $iが$ 入力キーの1つであるときに位置 $i$ に1ビットを置いてビットベクトルとして表現し、次に最下位ビットを繰り返し削除することで線形時間でソートできる。^[16]

Albers と Hagerup (1997) の非保守的なパックソートアルゴリズムでは、Ken Batcherのバイトニックソートネットワークに基づくサブルーチンを使用して、それぞれが 1 つのマシンワードにパックできるほど短い 2 つのソート済みキーシーケンスをマージします。パックソートアルゴリズムへの入力 (ワードごとに 1 つ格納される項目のシーケンス) は、このサブルーチンを繰り返し使用して各ワードにパックされる項目の数を 2 倍にすることで、パック形式 (ソートされた順序で複数の項目を保持するワードシーケンス) に変換されます。シーケンスがパック形式になると、Albers と Hagerup はマージソートの形式を使用してシーケンスをソートします。2 つのシーケンスを 1 つの長いシーケンスにマージする場合、同じバイトニックソートサブルーチンを使用して、2 つのシーケンスの残りの最小の要素で構成されるパックワードを繰り返し抽出できます。このアルゴリズムでは、パック表現から十分な高速化が得られるため、1 つのワードに $Ω(log n log log n)$ 個のキーを含めることができる場合は常に、入力を線形時間でソートできます。つまり、ある定数 $c$ $> 0に対して$ $log K log n log log n \leq cw$ の場合です。

少数のアイテムに対するアルゴリズム

ピジョンホールソート、カウンティングソート、基数ソート、およびファン・エムデ・ボアズ木ソートは、いずれもキーのサイズが小さいときに最もよく機能します。キーが十分に大きい場合、比較ソートアルゴリズムよりも遅くなります。ただし、キーのサイズまたはワードのサイズが項目の数に比べて非常に大きい場合 (または項目の数が少ない場合)、大きなワードに対して算術演算を実行する機能に固有の並列処理を利用するさまざまなアルゴリズムを使用して、再び高速にソートできるようになります。

この方向での初期の成果は、セルプローブ計算モデル（アルゴリズムの複雑さがメモリアクセスの回数のみで測定される人工モデル）を使用して、Ajtai、Fredman および Komlós（1984）によって提供されました。彼らの研究を基にして、Fredman と Willard（1994）は、ランダムアクセスマシンで実装可能な 2 つのデータ構造、Q ヒープとアトミックヒープについて説明しました。Q ヒープは、バイナリトライのビット並列バージョンであり、 $O ((log N) 1/4)$ 項目のセットに対して、優先キュー操作と後続クエリおよび先行クエリの両方を一定時間で実行できます。ここで、 $N \leq 2 w$ は、データ構造を実装するために必要な事前計算済みテーブルのサイズです。アトミックヒープは、各ツリーノードが Q ヒープとして表されるB ツリーです。これにより、 $(log N) O (1)$ 項目のセットに対して、優先キュー操作（およびソート）を一定時間で実行できます。

$Andersson ら (1998) は、任意の定数ε > 0$ に対して、一度に最大 $2 O ((log w) 1/2 - ε)$ 個の項目のセットを線形時間でソートできる、署名ソートと呼ばれるランダム化アルゴリズムを提供しています。Kirkpatrick と Reisch のアルゴリズムと同様に、彼らは、 $b$ を慎重に選んだ上で、キーを基数 $b$ の数値として表現して範囲縮小を実行します。彼らの範囲縮小アルゴリズムは、各桁を署名に置き換えます。署名は、異なる桁値が異なる署名を持つように $O$ $(log$ $n$ $)ビットのハッシュ値です$ $。n$ が十分に小さい場合、この置き換えプロセスによって形成される数値は元のキーよりも大幅に小さくなり、Albers と Hagerup (1997) の非保守的なパックソートアルゴリズムを使用して、置き換えられた数値を線形時間でソートできます。置き換えられた数字のソートされたリストから、線形時間でキーの圧縮されたトライを形成することができ、トライ内の各ノードの子はサイズ $b$ のキーのみを使用して再帰的にソートされ、その後ツリートラバーサルによってアイテムのソートされた順序が生成されます。

トランス二分法アルゴリズム

Fredman と Willard (1993) は、整数ソートアルゴリズムの解析のトランス二分モデルを導入しました。このモデルでは、整数キーの範囲については何も想定されておらず、データ値の数のみの関数によってアルゴリズムのパフォーマンスを制限する必要があります。あるいは、このモデルでは、 $n個の項目のセットに対するアルゴリズムの実行時間は、$ $K$ と $w$ の値のあらゆる可能な組み合わせに対する最悪の実行時間であると想定されます。このタイプの最初のアルゴリズムは Fredman と Willard の融合木ソートアルゴリズムで、実行時間は $O($ $n$ $log$ $n$ $/ log log$ $n$ $)です。これは、$ $K$ と $w$ の任意の選択に対して比較ソートよりも改善されています。乱数と整数除算演算の使用を含む彼らのアルゴリズムの代替バージョンでは、これが $O($ $n$ $\sqrt$ $log$ $n$ $)$ に改善されます。

彼らの研究以来、さらに優れたアルゴリズムが開発されている。例えば、カークパトリック・ライシュの範囲縮小法を、キーがアルバース・ハーゲルップのパックソートアルゴリズムを適用できるほど小さくなるまで繰り返し適用することで、 $O (n log log n)$ の時間でソートすることが可能になる。しかし、このアルゴリズムの範囲縮小部分には、大きなメモリ（ $\sqrt K$ に比例）またはハッシュテーブルの形でのランダム化が必要である。^[17]

$Han & Thorup (2002) は、ランダム時間O(n \sqrt log log n)$ でソートする方法を示した。彼らの手法では、シグネチャソートに関連するアイデアを使用して、データを多数の小さなサブリストに分割し、シグネチャソートでそれぞれを効率的にソートできるサイズにする。同様のアイデアを使用して、時間 $O (n log log n)$ と線形空間で決定論的に整数をソートすることもできる。^[18]単純な算術演算のみを使用して（乗算やテーブル参照なし）、ランダム期待時間 $O (n log log n)$ ^[19]または任意の定数 $ε > 0に対して時間$ $O (n (log log n) 1 + ε)$ で決定論的にソートすることができる。^[1]

参考文献

脚注

^ ハン＆ソルプ（2002年）。
^ フレッドマン＆ウィラード（1993年）。
^ 整数乗算やテーブル参照演算を許可すべきかどうかという問題は、Fredman & Willard (1993) に遡ります。また、Andersson、Miltersen & Thorup (1999) も参照してください。
^ リーフ (1985); Cole & Vishkin (1986) のコメント。ヘーゲルップ (1987);バットら。 (1991);アルバースとヘーゲルップ (1997)。
^ アガーワル＆ヴィッター（1988年）。
^ Farhadi et al. (2020).
^ ab Chowdhury (2008).
^ McIlroy、Bostic、McIlroy（1993）; Andersson、Nilsson（1998）。
^ ab ラーマン＆ラマン（1998）。
^ ペダーセン（1999年）。
^ DARPA HPCS 離散数学ベンチマーク Archived 2016-03-10 at the Wayback Machine、Duncan A. Buell、サウスカロライナ大学、2011-04-20 取得。
^ Goodrich & Tamassia (2002)。Cormen et al. (2001) もこのソートアルゴリズムのバージョンを説明していますが、彼らが説明しているバージョンは整数ソートではなく、キーが既知の分布を持つ実数である入力に適応しています。
^ Cormen et al. (2001)、8.2 カウンティングソート、pp.168-169。
^ Comrie (1929–1930); Cormen et al. (2001)、8.3 Radix Sort、pp. 170–173。
^ カークパトリックとライシュ (1984);アルバースとヘーゲルップ (1997)。
^ カークパトリックとライシュ (1984)。
^ アンダーソンら（1998年）。
^ ハン（2004年）。
^ ソールプ（2002）

二次資料

Chowdhury, Rezaul A. (2008)、「優先キューとソートの等価性」、Kao, Ming-Yang (編)、Encyclopedia of Algorithms、Springer、pp. 278–281、ISBN 9780387307701。
コーメン、トーマス H. ;レイザーソン、チャールズ E. ;リベスト、ロナルド L. ;スタイン、クリフォード(2001)、『アルゴリズム入門(第 2 版)』、MIT プレスおよびMcGraw-Hill、ISBN 0-262-03293-7。
Goodrich, Michael T. ; Tamassia, Roberto (2002)、「4.5 バケットソートと基数ソート」、アルゴリズム設計: 基礎、分析、およびインターネットの例、John Wiley & Sons、pp. 241–243。

一次資料

Aggarwal, Alok; Vitter, Jeffrey S. (1988 年 9 月)、「ソートおよび関連問題の入出力の複雑さ」、Communications of the ACM、31 (9): 1116–1127、doi : 10.1145/48529.48535、S2CID 6264984
Ajtai, M. ; Fredman, M. ; Komlós, J. (1984)、「優先キューのハッシュ関数」、情報制御、63 (3): 217–225、doi : 10.1016/S0019-9958(84)80015-7、MR 0837087。
Albers, Susanne ; Hagerup, Torben (1997)、「同時書き込みなしの並列整数ソートの改善」、Information and Computation、136 (1): 25–51、CiteSeerX 10.1.1.53.498、doi :10.1006/inco.1997.2632、MR 1457693、S2CID 1284673。
アンダーソン、アルネ。ヘイゲルップ、トーベン。ニルソン、ステファン。 Raman、Rajeev (1998)、「線形時間での並べ替え?」、Journal of Computer and System Sciences、57 (1): 74–93、doi : 10.1006/jcss.1998.1580、MR 1649809。
Andersson, Arne; Nilsson, Stefan (1998)、「radixsort の実装」、ACM Journal of Experimental Algorithmics、3 : 7–es、CiteSeerX 10.1.1.54.4536、doi :10.1145/297096.297136、MR 1717389、S2CID 2125652。
Andersson, Arne; Miltersen, Peter Bro; Thorup, Mikkel (1999)、「フュージョンツリーは $AC 0$ 命令のみで実装可能」、Theoretical Computer Science、215 (1–2): 337–344、CiteSeerX 10.1.1.32.9401、doi :10.1016/S0304-3975(98)00172-8、MR 1678804。
Bhatt, PCP; Diks, K.; Hagerup, T.; Prasad, VC; Radzik, T.; Saxena, S. (1991)、「改善された決定論的並列整数ソート」、Information and Computation、94 (1): 29–47、doi : 10.1016/0890-5401(91)90031-V、MR 1123154。
Cole, R.; Vishkin, U. (1986)、「決定論的コイン投げと最適並列リストランキングへの応用」、情報制御、70 (1): 32–53、doi : 10.1016/S0019-9958(86)80023-7。
コムリー、LJ (1929–1930)、「ホレリスとパワーズの集計機」、トランス、オフィス・マシン・ユーザーズ・アソシエーション、LTD.、25–37Thorup (2007) によって基数ソートの初期のソースとして引用されています。
Farhadi, Alireza; Hajiaghayi, Mohammad Taghi ; Larsen, Kasper Green; Shi, Elaine (2020 年 9 月)、「ネットワークコーディングによる外部メモリ整数ソートの下限値」、Communications of the ACM、63 (10): 97–105、arXiv : 1811.01313、doi :10.1145/3416268、S2CID 221865838。
Fredman, Michael L. ; Willard, Dan E. (1993)、「融合木による情報理論的限界の超越」、Journal of Computer and System Sciences、47 (3): 424–436、doi : 10.1016/0022-0000(93)90040-4、MR 1248864。
Fredman, Michael L. ; Willard, Dan E. (1994)、「最小全域木と最短経路のためのトランス二分法アルゴリズム」、Journal of Computer and System Sciences、48 (3): 533–551、doi : 10.1016/S0022-0000(05)80064-9、MR 1279413。
Hagerup, Torben (1987)、「最適な並列バケットソートに向けて」、情報と計算、75 (1): 39–51、doi : 10.1016/0890-5401(87)90062-9、MR 0910976。
$Han, Yijie (2004)、「 O (n log log n)$ 時間と線形空間での決定論的ソート」、 Journal of Algorithms、50 (1): 96–105、doi :10.1016/j.jalgor.2003.09.001、MR 2028585。
Han, Yijie; Thorup, M. (2002)、「 $O(n \sqrt log log n)$ の期待時間と線形空間での整数ソート」、第 43 回コンピュータサイエンスの基礎に関する年次シンポジウム (FOCS 2002) の議事録、IEEE コンピュータソサエティ、pp. 135–144、doi :10.1109/SFCS.2002.1181890、S2CID 5245628。
カークパトリック、デイビッド、ライシュ、ステファン（1984）、「ランダムアクセスマシンでの整数ソートの上限」、理論計算機科学、28（3）：263–276、doi：10.1016/0304-3975（83）90023-3、MR 0742289。
McIlroy, Peter M.; Bostic, Keith; McIlroy, M. Douglas (1993)、「エンジニアリング基数ソート」(PDF)、コンピューティングシステム、6 (1): 5–27。
Pedersen, Morten Nicolaj (1999)、内部整数ソートのためのワード RAM アルゴリズムの実際的意義の研究、修士論文、コンピューターサイエンス学部、コペンハーゲン大学、デンマーク、2012 年 3 月 16 日にオリジナルからアーカイブ、 2011 年 4 月 21日に取得。
Rahman, Naila; Raman, Rajeev (1998)、「いくつかのソートアルゴリズムにおけるワードレベルの並列処理の実験的研究」、アルゴリズムエンジニアリング、第 2 回国際ワークショップ、WAE '92、ザールブリュッケン、ドイツ、1998 年 8 月 20 ～ 22 日、議事録(PDF)、マックスプランクコンピュータサイエンス研究所、pp. 193 ～ 203。
ライフ、ジョン H. (1985)、「整数ソートのための最適な並列アルゴリズム」、第 26 回コンピュータサイエンスの基礎に関する年次シンポジウム (FOCS 1985) の議事録、IEEE コンピュータソサエティ、pp. 496–504、doi :10.1109/SFCS.1985.9、ISBN 0-8186-0644-4、S2CID 5694693。
Thorup, Mikkel (2002)、「加算、シフト、およびビット単位のブール演算を使用した $O (n log log n)$ 時間と線形空間でのランダムソート」、Journal of Algorithms、42 (2): 205–230、CiteSeerX 10.1.1.55.4443、doi :10.1006/jagm.2002.1211、MR 1895974、S2CID 9700543。
Thorup, Mikkel (2003)、「 $AC 0 の$ 融合木とアトミックヒープの実装について」、第 14 回 ACM-SIAM 離散アルゴリズムシンポジウムの議事録 (メリーランド州ボルチモア、2003)、ニューヨーク: ACM、pp. 699–707、ISBN 978-0-89871-538-5、MR 1974982。
Thorup, Mikkel (2007)、「優先キューとソートの同等性」、Journal of the ACM、54 (6): Art. 28、doi :10.1145/1314690.1314692、MR 2374029。
ウィラード、ダン E. (1983)、「対数対数最悪ケース範囲クエリは空間 $Θ(N)$ で可能である」、情報処理レター、17 (2): 81–84、doi :10.1016/0020-0190(83)90075-3、MR 0731126。

[ht02-1] ハン＆ソルプ（2002年）。

[2] フレッドマン＆ウィラード（1993年）。

[3] 整数乗算やテーブル参照演算を許可すべきかどうかという問題は、Fredman & Willard (1993) に遡ります。また、Andersson、Miltersen & Thorup (1999) も参照してください。

[4] リーフ (1985); Cole & Vishkin (1986) のコメント。ヘーゲルップ (1987);バットら。 (1991);アルバースとヘーゲルップ (1997)。

[FOOTNOTEAggarwalVitter1988-5] アガーワル＆ヴィッター（1988年）。

[FOOTNOTEFarhadiHajiaghayiLarsenShi2020-6] Farhadi et al. (2020).

[FOOTNOTEChowdhury2008-7] Chowdhury (2008).

[8] McIlroy、Bostic、McIlroy（1993）; Andersson、Nilsson（1998）。

[rr98-9] ラーマン＆ラマン（1998）。

[10] ペダーセン（1999年）。

[11] DARPA HPCS 離散数学ベンチマーク Archived 2016-03-10 at the Wayback Machine、Duncan A. Buell、サウスカロライナ大学、2011-04-20 取得。

[12] Goodrich & Tamassia (2002)。Cormen et al. (2001) もこのソートアルゴリズムのバージョンを説明していますが、彼らが説明しているバージョンは整数ソートではなく、キーが既知の分布を持つ実数である入力に適応しています。

[13] Cormen et al. (2001)、8.2 カウンティングソート、pp.168-169。

[14] Comrie (1929–1930); Cormen et al. (2001)、8.3 Radix Sort、pp. 170–173。

[15] カークパトリックとライシュ (1984);アルバースとヘーゲルップ (1997)。

[16] カークパトリックとライシュ (1984)。

[17] アンダーソンら（1998年）。

[18] ハン（2004年）。

[19] ソールプ（2002）