Block_sort
ブロックソート圧縮
と混同しないでください
ブロックソート、またはブロックマージソートは、少なくとも2つのマージ操作と挿入ソートを組み合わせてO（n log n）のインプレース安定ソートに到達するソートアルゴリズムです。2つのソートされたリストAとBをマージすることは、Aを均等なサイズのブロックに分割し、特別なルールの下で各AブロックをBに挿入し、ABペアをマージすることと同等であるという観察からその名前が付けられています。
ブロックソート
ソート安定16に数字1をソーティングブロック 抽出二つの内部バッファ、タグ16の挿入ソートグループ
Aの（サイズのブロック
√ 16 = 4毎）、ロール
Aを介してブロック
B、ローカルにマージソート第2のバッファ、バッファを再配布します。
クラス
ソートアルゴリズム
データ構造
配列
最悪の場合の パフォーマンス
O（n log n）
最高の パフォーマンス （n） 平均 パフォーマンス
O（n log n）
最悪の場合の スペースの複雑さ （1） O（log n）インプレースマージの実用的なアルゴリズムの1つが、2008年にPok-SonKimとArneKutznerによって提案されました。
コンテンツ
1 概要
2 アルゴリズム
2.1 アウターループ 2.2 バッファを抽出します 2.3 タグAブロック 2.4 ロールアンドドロップ 2.5 ローカルマージ 2.62.6 再配布
3 バリアント
4 分析
4.1 複雑 4.2 メモリー 4.3 安定 4.4 適応性
5 利点
6 短所
7 参考文献
概要
ブロックソートの外側のループは、ボトムアップマージソートと同じです。ソートの各レベルは、サイズが1、2、4、8、16などのサブ配列のペアAとBをマージします。結合された両方のサブ配列が配列自体になるまで。
むしろマージよりAおよびBを従来の方法と同様に、直接、ブロック・ベースのマージアルゴリズム分割のAサイズの離散的なブロックに√ A（その結果√ Aの 数だけでなく、ブロック）、各インサートのAにブロックBとなるように各Aブロックの最初の値はその直後のB値以下（≤）であり、次に各Aブロックをそのブロックと次のAブロックの間の任意のB値とローカルにマージします。
マージには、マージするAブロックを保持するのに十分な大きさの個別のバッファーが必要なため、配列内の2つの領域がこの目的のために予約されています（内部バッファーと呼ばれます）。したがって、最初の2つのAブロックは、A内の各値の最初のインスタンスを含むように変更され、必要に応じてそれらのブロックの元の内容がシフトされます。次に、残りのAブロックがBに挿入され、2つのバッファの1つをスワップスペースとして使用してマージされます。このプロセスにより、そのバッファー内の値が再配置されます。
すべてのAおよびBサブアレイのすべてのAおよびBブロックが、そのレベルのマージソートでマージされたら、そのバッファー内の値をソートして元の順序に戻す必要があるため、挿入ソートを適用する必要が次に、バッファ内の値は、配列内の最初にソートされた位置に再配布されます。このプロセスは、外側のボトムアップマージソートの各レベルで繰り返され、その時点で配列は安定してソートされます。
アルゴリズム
コード例では、次の演算子が使用されています。
| ビットごとのOR
>> 右シフト
％ モジュロ++および+ = インクリメント
[ x、y）
範囲≥からのxおよび< Y
|範囲| range.end – range.start
配列 配列のi番目の項目
さらに、ブロックソートは、全体的なアルゴリズムの一部として次の操作に依存しています。
スワップ：配列内の2つの値の位置を交換します。
ブロックスワップ：配列内の値の範囲を、配列の異なる範囲内の値と交換します。
二分探索：配列がソートされていると仮定して、現在の検索範囲の中央の値を確認し、値が小さい場合は下限を確認し、値が大きい場合は上限を確認します。ブロックソートは2つのバリアントを使用します。1つはソートされた配列に値を挿入する最初の位置を検索し、もう1つは最後の位置を検索します。
線形検索：すべての要素を順番にチェックして、配列内の特定の値を見つけます。
挿入ソート：配列内の各アイテムについて、後方にループして挿入する必要のある場所を見つけ、その位置に挿入します。
配列の回転：配列内のアイテムをいくつかのスペースだけ左または右に移動し、エッジの値を反対側に折り返します。回転は、3回の反転として実装できます。
Rotate（array、amount、range） Reverse（array、range） Reverse（array、[range.start、range.start + amount）） Reverse（array、[range.start + amount、range.end））
2のフロアパワー：値を次の2のパワーにフロアします。したがって、63は32になり、64は64のままになります。
FloorPowerOfTwo（x） x = x | （x >> 1） x = x | （x >> 2） x = x | （x >> 4） x = x | （x >> 8） x = x | （x >> 16） if（これは64ビットシステムです）
x = x | （x >> 32） xを返す-（x >> 1）
アウターループ
前に述べたように、ブロックソートの外側のループはボトムアップマージソートと同じです。ただし、各AおよびBサブアレイが1つのアイテム内で同じサイズであることを保証するバリアントの恩恵を受けます。
BlockSort（配列）power_of_two= FloorPowerOfTwo（array.size）
規模= array.size / power_of_two // 1.0≤規模<2.0
//挿入ソート時16-31アイテム
のための（マージ= 0;マージ
終了=開始+ 16 *スケール
InsertionSort（array、[start、end））
for（length = 16; length
mid =（マージ+長さ）*スケール
終了=（マージ+長さ* 2）*スケール
if（array
Rotate（array、mid − start、[start、end））
else if（array > array ）
Merge（array、A = [start、mid）、B = [mid、end））
//それ以外の場合、範囲はすでに正しく順序付けられています
スケールファクターを分数として表すことにより、固定小数点演算を使用することもできますinteger_part + numerator/denominator。
power_of_two = FloorPowerOfTwo（array.size） 分母= power_of_two / 16 numerator_step = array.size％分母 integer_step = floor（array.size / denominator） //一度に16〜31個のアイテムを挿入ソート while（integer_step
while（integer_part
start = integer_part
integer_part + = integer_step
分子+ = numerator_step
if（分子≥分母）
分子-=分母
integer_part ++
mid = integer_part
integer_part + = integer_step
分子+ = numerator_step
if（分子≥分母）
分子-=分母
integer_part ++
end = integer_part
if（array
else if（array > array ）
Merge（array、A = [ start、mid）、B = [mid、end））
integer_step + = integer_step
numerator_step + = numerator_step
if（numerator_step≥分母）
numerator_step − =分母
integer_step ++
バッファを抽出します タグAブロック ロールアンドドロップ ローカルマージ 再配布 バリアント 分析 複雑 メモリー 安定 適応性 利点 短所 参考文献
ブロックソートのバッファ抽出プロセス。
マージステップの各レベルに必要な2つの内部バッファは、第2移動させることによって作成される√ Aの内の各値のインスタンスAの開始にサブアレイA。最初にAの要素を繰り返し処理し、必要な一意の値をカウントします。次に、配列の回転を適用して、それらの一意の値を先頭に移動します。 Aは、（サイズの2つのバッファを満たすのに十分な一意の値が含まれていなかった場合√ Aずつ）、Bはちょうど同様に使用することができます。この場合、移動最後に、各値のインスタンスの終了のBの部分と、Bマージ中に含まれ
while（integer_step
buffer_size = block_size = integer_step / buffer_size + 1 integer_part =分子= 0while（integer_part
最初の内部バッファからの値を使用してAブロックにタグを付け
ます。最初のAブロックと最後の
Bブロックのサイズが不均一であることに注意してください 1つまたは2つの内部バッファーが作成されると、このレベルのマージソートの各AおよびBサブアレイのマージが開始されます。そのために、各AおよびBサブアレイを、前の手順で計算したサイズの均等なサイズのブロックに分割します。最初のAブロックと最後のBブロックは、必要に応じて不均等なサイズになります。次に、均等なサイズのAブロックのそれぞれをループし、2番目の値を2つの内部バッファーの最初の値からの対応する値と交換します。これは、ブロックのタグ付けとして知られています。
// blockAは残りのAブロックの範囲であり、// firstAは不均一なサイズの最初のAブロックですblockA = [A.start、A.end）firstA = [A.start、A.start + | blockA | ％block_size） //各Aブロックの2番目の値をbuffer1の値とスワップします（index = 0、indexA = firstA.end + 1; indexA
Bブロックを転がる2つのAブロック。最初のAブロックが遅れると、サイズが不均一なAブロックは、それに続くB値とローカルにマージされます。
この方法でAブロックを定義してタグ付けした後、最初の均等なサイズのAブロックを次のBブロックとブロック交換することにより、AブロックがBブロックを介してロールされます。このプロセスは、タグ値が最小のAブロックの最初の値が、Aブロックと交換されたばかりのBブロックの最後の値以下になるまで繰り返されます。
その時点で、最小のAブロック（タグ値が最小のAブロック）がローリングAブロックの先頭にスワップされ、タグ付けされた値が最初のバッファーからの元の値で復元されます。これは、残りのAブロックと一緒にロールされなくなるため、ブロックを後ろにドロップすることとして知られています。次に、そのAブロックが前のBブロックに挿入されます。まず、Bで二分探索を使用して、Aの最初の値がBのそのインデックスの値以下であるインデックスを見つけ、次にAを次のようにローテーションします。そのインデックスでB。
minA = blockA.start indexA = 0 while（true）
//前のBブロックがあり、最小Aブロックの最初の値が≤
//前のBブロックの最後の値である場合、その最小Aブロックを後ろにドロップします。
//または、Bブロックが残っていない場合は、残りのAブロックを削除し続けます。
if（（| lastB |> 0 and array ≥array）or | blockB | = 0）
//前のBブロックを分割する場所を
見つけ、分割B_split =で回転するBinaryFirst（array、array 、lastB）
B_remaining = lastB.end-B_split
//最小のAブロックをローリングAブロックの先頭にスワップします
BlockSwap（array、blockA.start、minA、block_size）
// Aブロック
スワップの2番目の値を復元します（array [blockA.start + 1]、array [buffer1.start + indexA]）
indexA ++
// Aブロックを前のBブロックに
回転しますRotate（array、blockA.start-B_split、[B_split、blockA.start + block_size））
//前のAブロックをそれに続くB値とローカルにマージします
。//2番目の内部バッファーをスワップスペースとして使用します（存在する場合）
if（| buffer2 |> 0）
MergeInternal（array、lastA、[lastA.end、 B_split）、buffer2） else MergeInPlace（array、lastA、[lastA.end、B_split））
//残りのAブロックの範囲を更新し、
//分割後にBブロックから残っている範囲を更新します
lastA = [blockA.start-B_remaining、blockA.start-B_remaining + block_size）
lastB = [lastA.end、lastA.end + B_remaining）
// Aブロックが残っていない場合、このステップは終了します
blockA.start = blockA.start + block_size
if（| blockA | = 0） break minA = （以下を参照）
else if（| blockB |
lastB = [blockA.start、blockA.start + | blockB |）
blockA.start + = | blockB |
blockA.end + = | blockB |
minA + = | blockB |
blockB.end = blockB.start else //左端のAブロックを次のBブロックと交換して最後までロールします
BlockSwap（array、blockA.start、blockB.start、block_size）
lastB = [blockA.start、blockA.start + block_size）
if（minA = blockA.start）
minA = blockA.end
blockA.start + = block_size
blockA.end + = block_size
blockB.start + = block_size
//これはminimum（blockB.end + block_size、B.end）と同等ですが、 // （blockB.end> B.end –block_size）の場合はオーバーフローする可能性があります
blockB.end = B.end
そうしないと
blockB.end + = block_size //最後のAブロックを残りのB値とマージします if（| buffer2 |> 0）
MergeInternal（array、lastA、[lastA.end、B.end）、buffer2） else
MergeInPlace（array、lastA、[lastA.end、曲げる））
このステップで適用できる最適化の1つは、フローティングホール手法です。最小のAブロックが遅れて、前のBブロックにローテーションする必要があり、その後、その内容がローカルマージのために2番目の内部バッファーにスワップされる場合、Aブロックをバッファーにスワップする方が高速です。事前に、そしてそのバッファの内容が順序を保持する必要がないという事実を利用するために。したがって、2番目のバッファー（ブロックスワップの前はAブロックでした）を位置インデックスの前のBブロックにローテーションするのではなく、インデックスの後のBブロックの値をバッファーの最後のアイテムと単純にブロックスワップできます。
この場合のフローティングホールとは、配列の周りにフローティングしている2番目の内部バッファの内容を指し、アイテムが順序を保持する必要がないという意味でホールとして機能します。
AブロックがBブロックにローテーションされると、前のAブロックは、2番目のバッファーをスワップスペースとして使用して、それに続くB値とマージされます。最初のAブロックが後ろにドロップされた場合、これは開始時に不均一なサイズのAブロックを指し、2番目のAブロックが後ろにドロップされた場合、最初のAブロックを意味します。
MergeInternal（array、A、B、buffer）
// Aの値を ‘buffer’の値とブロックスワップします
BlockSwap（array、A.start、buffer.start、| A |）
A_count = 0、B_count = 0、insert = 0
while（A_count <| A |およびB_count <| B |）
if（array [buffer.start + A_count]≤array[B.start + B_count]）
Swap（array [A.start + insert]、array [buffer.start + A_count]）
A_count ++ else スワップ（array [A.start + insert]、array [B.start + B_count]）
B_count ++
挿入++
//バッファの残りの部分を配列の残りの部分とブロックスワップします
BlockSwap（array、buffer.start + A_count、A.start + insert、| A | –A_count）
2番目のバッファーが存在しない場合は、ローテーションベースバージョンのHwang and Linアルゴリズム Dudzinski and Dydekアルゴリズムなど、厳密にインプレースマージ操作を実行する必要が二分探索と回転を繰り返しました。
MergeInPlace（array、A、B）
while（| A |> 0 and | B |> 0）
// Aの最初の項目を挿入する必要があるBの最初の場所を見つける
mid = BinaryFirst（array、array 、B）
// Aを所定の位置に回転させます
金額=中間-A.end
回転（配列、量、[A。開始、中間））
//新しいAとBの範囲を計算します
B = [mid、B.end）
A = [A.start + amount、mid）
A.start = BinaryLast（array、array 、A）
最小Aブロックを削除し、前のAブロックをそれに続くB値とマージした後、新しい最小Aブロックは、まだ配列を介してロールされているブロック内で見つける必要がこれは、これらのAブロックを線形検索し、タグ値を比較して最小のものを見つけることによって処理されます。
minA = blockA.start for（findA = minA + block_size; findA
これらの残りのAブロックは、アレイ内をローリングし続け、それらが属する場所にドロップおよび挿入されます。このプロセスは、すべてのAブロックがドロップされ、前のBブロックにローテーションされるまで繰り返されます。
最後に残ったAブロックがドロップされ、それが属するBに挿入されたら、それに続く残りのB値とマージする必要がこれで、AサブアレイとBサブアレイの特定のペアのマージプロセスが完了します。ただし、マージソートの現在のレベルの残りのAおよびBサブアレイに対してプロセスを繰り返す必要が
内部バッファは、このレベルのマージソートのAおよびBサブアレイのすべてのセットで再利用でき、再抽出または変更する必要がないことに注意して
すべてのAサブアレイとBサブアレイがマージされた後も、1つまたは2つの内部バッファーが残っています。最初の内部バッファーはAブロックのタグ付けに使用され、その内容は以前と同じ順序のままですが、2番目の内部バッファーは、マージのスワップスペースとして使用されたときに内容が再配置された可能性がこれは、2番目のバッファの内容を、挿入ソートなどの別のアルゴリズムを使用してソートする必要があることを意味します。次に、2つのバッファを作成するために使用されたのとは逆のプロセスを使用して、2つのバッファをアレイに再配布する必要が
ボトムアップマージソートのすべてのレベルでこれらの手順を繰り返した後、ブロックソートが完了します。
ブロックソートは、2つの内部バッファーを抽出し、AおよびBサブアレイを均等なサイズのブロックに分割し、AブロックをロールしてBにドロップし（最初のバッファーを使用してAブロックの順序を追跡し）、2番目のバッファーをスワップとしてローカルにマージすることで機能します。スペース、2番目のバッファーのソート、および両方のバッファーの再配布。手順は変更されませんが、これらのサブシステムは実際の実装が異なる場合が
ブロックソートの1つの変形では、Aが収まるたびに、この外部バッファを使用してAサブアレイまたはAブロックをBとマージすることにより、提供された任意の量の追加メモリを使用できます。この状況では、マージソートと同じになります。
バッファサイズの適切な選択は次のとおりです。
サイズ ノート（カウント+ 1）/ 2 すべてのAサブアレイがそれに適合するため、フルスピードのマージソートになります
√ （カウント+ 1）/ 2 + 1
これは、マージの最大レベルでのAブロックのサイズになるため、ブロックの並べ替えでは、内部マージまたはインプレースマージを使用してスキップできます。
512 マージソートのより小さなレベルで多数のマージを処理するのに十分な大きさの固定サイズのバッファ
0 システムが追加のメモリを割り当てることができない場合、メモリはうまく機能しません
内部バッファの1つの内容を使用してAブロックにタグを付けるのではなく、代わりに間接移動模倣バッファを使用できます。 これは、s1 t s2として定義される内部バッファーです。ここで、s1とs2はそれぞれAブロックとBブロックの数と同じ大きさであり、tにはs1の直後の最後の値に等しい値が含まれます。s1（したがって、s2の値がs1に表示されないようにします）。含む第2内部バッファ√一意の値が引き続き使用されます。第√ Aの値S1とS2は次いでブロックはブロックであり、Bブロックがあるかについてのバッファに符号化情報を相互に交換されます。インデックスiのAブロックがインデックスjのBブロックと交換されると（最初の均等なサイズのAブロックは最初はインデックス0にあります）、s1 とs1 はs2 とs2 、それぞれ。これは、AブロックがBを通過する動きを模倣します。2番目のバッファーの一意の値は、AブロックがBブロックを通過するときにAブロックの元の順序を決定するために使用されます。すべてのAブロックが削除されると、移動模倣バッファーを使用して、配列内の特定のブロックがAブロックであるかBブロックであるかがデコードされ、各AブロックがBにローテーションされ、2番目の内部バッファーが使用されます。ローカルマージのスワップスペースとして。
各Aブロックの2番目の値は、必ずしもタグ付けする必要はありません。代わりに、最初、最後、またはその他の要素を使用できます。ただし、最初の値がタグ付けされている場合、最小Aブロックをドロップする場所を決定するときに、最初の内部バッファー（スワップされた場所）から値を読み取る必要が
バッファの内容は一意であることが保証されているため、クイックソートなどの不安定な並べ替えを含め、多くの並べ替えアルゴリズムを使用して2番目の内部バッファの内容を並べ替えることができます。ただし、状況に応じたパフォーマンスと再帰の欠如のため、挿入ソートは依然として推奨されます。
ブロックソートは、明確に定義されたテスト可能なクラスのアルゴリズムであり、マージおよびソートとして機能する実装を利用できます。 これにより、その特性を測定および検討することができます。
ブロックソートは、配列内の16〜31アイテムのグループに対して挿入ソートを実行することから始まります。挿入ソートでO（N 2）からの任意の場所にこのリードので、運転O（16 2 × N / 16）にO（31 2 × N / 31）で、O（N）回定数因子が省略されています。また、各レベルのマージが完了した後、2番目の内部バッファに挿入ソートを適用する必要がしかし、このバッファのように限られた√ A、サイズがO（√ N 2）動作もなってしまうO（N）。
次に、マージソートのレベルごとに2つの内部バッファを抽出する必要がこれは、AおよびBサブ配列内の項目を反復処理し、値が変更されるたびにカウンターをインクリメントすることによって行われます。十分な値が見つかると、Aの先頭またはBの末尾に回転します。最悪の場合、これは最終的になります。√Aの非連続の一意の値を見つける前に配列全体を検索します。これには、O（n）の比較と√Aの値の√Aの回転が必要です。この解決さO（N + √ N × √ N）、又はO（N）。
AまたはBサブアレイのいずれにも内部バッファーを作成するための√Aの一意の値が含まれていない場合、通常は次善のインプレースマージ操作が実行され、AがBにバイナリ検索およびローテーションが繰り返されます。サブアレイ再びこのステップの間に実行されるバイナリ検索し、回転数のハード制限、場所√ Aのアイテムをまで回転√ Aの時間、またはO（N）。各ブロックのサイズは、それが見つかった場合には小さくなるように調整されている√ユニークな値ではなく2 √ A一意の値の数は、任意のA又はBブロック内に含まれる更なる制限を、。
Aブロックをタグ付けが行われる√各Aサブアレイの時間を、次いで、Aブロックはを通じてロールとにBブロックにまで挿入されている√ Aの時間。ローカルマージは、値をコピーするのではなくスワップする必要があるため、割り当てが多くなりますが、標準マージと同じO（n）の複雑さを保持します。上の新しい最小のAブロックの繰り返し処理を見つけるための線形検索√ブロック√ Aの時間。また、バッファの再配布プロセスはバッファの抽出と同じですが、逆であるため、O（n）の複雑さは同じです。
最も高い複雑さを除くすべてを省略し、外側のマージループにlog nレベルがあることを考慮した後、これは最悪の場合と平均的な場合のO（n log n）の最終的な漸近的な複雑さにつながります。データがすでに整理されている最良の場合、マージステップは最初のレベルでn / 16の比較を実行し、次にn / 32、n / 64、n / 128などを実行します。これはよく知られている数学シリーズです。O（n）に解決されます。
ブロックの並べ替えは非再帰的であり、動的な割り当てを使用する必要がないため、これにより、スタックとヒープのスペースが一定になります。トランス二分モデルでO（1）補助メモリを使用します。これは、AおよびBの範囲を追跡するために必要なO（log n）ビットが32ビットまたは64ビットで32または64を超えることはできないことを受け入れます。それぞれコンピューティングシステムであるため、実行可能な割り当てが可能な任意のアレイのO（1）スペースに簡略化されます。
配列内のアイテムはブロックの並べ替え中に順序が狂っていますが、各操作は完全に元に戻すことができ、完了するまでに同等のアイテムの元の順序に戻ります。
安定性を確保するには、並べ替え前の配列内の各値の最初のインスタンスが、並べ替え後もその値の最初のインスタンスである必要がブロックソートは、これらの最初のインスタンスを配列の先頭に移動して2つの内部バッファーを作成しますが、ブロックソートの現在のレベルですべてのマージが完了すると、これらの値は配列内の最初にソートされた位置に戻されます。これにより、安定性が維持されます。
AブロックをBブロックにロールする前に、各Aブロックの2番目の値が最初のバッファーの値と交換されます。その時点で、AブロックはBブロックをロールスルーするために順不同に移動します。ただし、最小のAブロックを前のBブロックに挿入する場所が見つかると、その最小のAブロックはAブロックの先頭に戻され、2番目の値が復元されます。すべてのAブロックが挿入されるまでに、Aブロックは再び順番になり、最初のバッファーには元の値が元の順序で含まれます。
AブロックをいくつかのB値とマージするときに、2番目のバッファーをスワップスペースとして使用すると、そのバッファーの内容が再配置されます。ただし、アルゴリズムではバッファに一意の値のみが含まれることがすでに保証されているため、バッファの内容を並べ替えるだけで、元の安定した順序を復元できます。
ブロックソートは、2つのレベルでの適応ソートです。最初に、すでに順序付けられているAサブアレイとBサブアレイのマージをスキップします。次に、AとBをマージする必要があり、均等なサイズのブロックに分割される場合、Aブロックは必要な範囲でのみBを介してロールされ、各ブロックはその直後のB値とのみマージされます。元々データの順序が多ければ多いほど、Aにマージする必要のあるB値は少なくなります。
ブロックソートは、追加のメモリを必要としない安定したソートです。これは、O（n）バッファを割り当てるのに十分な空きメモリがない場合に役立ちます。ブロックソートの外部バッファバリアントを使用する場合、O（n）メモリの使用から、必要に応じて徐々に小さくなるバッファに拡張でき、それらの制約内で効率的に機能します。
ブロックソートは、Timsortなどの他のアルゴリズムほど細かいレベルでソートされたデータ範囲を利用しません。 AとBのサブアレイ、およびAとBのブロックという2つの事前定義されたレベルでこれらのソートされた範囲のみをチェックします。また、マージソートと比較して、実装と並列化が困難です。
^ Kutzner、Arne; キム、ポクソン（2008）。比率ベースの安定したインプレースマージ （PDF）。コンピュータサイエンスの講義ノート。4978。シュプリンガーベルリンハイデルベルク。pp。246–257 。
^ マンニラ、ヘイッキ; ウッコネン、エスコ（1984年5月14日）。「その場でのマージのための単純な線形時間アルゴリズム」。情報処理レター。18（4）：203–208。土井：10.1016 / 0020-0190（84）90112-1。
^ クロンロッド、M。アレクサンダー（1969年2月）。”Оптимальныйалгоритмупорядочениябезрабочегополя” [操作フィールドのない最適な順序付けアルゴリズム]。USSR科学アカデミーの議事録（ロシア語）。186（6）：1256–1258。
^ ベントレー、ジョン（2006）。プログラミングパール（第2版）。
^ ウォーレンジュニア、ヘンリーS.（2013）。ハッカーの喜び（2版）。アディソンウェズリー-ピアソンエデュケーション社ISBN 978-0-321-84268-8。0-321-84268-5。
^ Pardo、Luis Trabb（1977）。最適な空間と時間の境界を使用した安定した並べ替えとマージ。SIAMジャーナルオンコンピューティング。6。pp。351–372。
^ Geffert、Viliam; Katajainen、Jykri; パサネン、トミ。「漸近的に効率的なインプレースマージ」。理論計算機科学。237（1–2）：159–181。CiteSeerX 10.1.1.22.5750。土井：10.1016 / S0304-3975（98）00162-5。
^ ファン、FK; リン、S。（1972）。2つの互いに素な線形順序集合をマージするための単純なアルゴリズム。SIAMジャーナルオンコンピューティング。1。pp。31–39。土井：10.1137 / 0201004。ISSN 0097から5397まで。
^ Dudzinski、Krzysztof; Dydek、Andrzej（1981）。安定したストレージマージアルゴリズムについて。情報処理レター。12。pp。5–8。
^ Symvonis、Antonios（1995）。「最適な安定したマージ」。コンピュータジャーナル。38（8）：681–690。CiteSeerX 10.1.1.55.6058。土井：10.1093 / comjnl /38.8.681。
^ ArneKutzner。「インプレースマージアルゴリズムベンチマークツール」。
^ ArneKutzner。「インプレースマージアルゴリズムベンチマークツール」。
^ 「C、C ++、およびJavaのブロックソートのパブリックドメイン実装」。
^ ティム・ピーターズ。「Re：WikiSort」。”