ブロックソート

前述のとおり、ブロックソートの外側のループはボトムアップマージソートと同一です。ただし、 AとBの各サブ配列のサイズが1要素の誤差範囲内で同じになるようにするバリアントが採用されています。

ブロックソート（配列） power_of_two = FloorPowerOfTwo (array.size) scale = array.size/power_of_two // 1.0 ≤ scale < 2.0// 挿入ソート 16～31個の項目を一度に処理for (merge = 0; merge < power_of_two; merge += 16) 開始 = マージ * スケール 終了 = 開始 + 16 * スケール 挿入ソート（配列、[開始、終了） for (length = 16; length < power_of_two; length += length) for (merge = 0; merge < power_of_two; merge += length * 2) 開始 = マージ * スケール 中間値 = (マージ + 長さ) * スケール end = (merge + length * 2) * scale if (array[end − 1] < array[start]) // 2 つの範囲が逆順になっているため、回転するだけでマージできますRotate (array, mid − start, [start, end)) else if (array[mid − 1] > array[mid]) Merge (array, A = [start, mid), B = [mid, end)) // それ以外の場合は、範囲は既に正しい順序になっています

固定小数点演算も使用でき、その場合はスケールファクターを分数で表しますinteger_part + numerator/denominator。

ブロックソート（配列） power_of_two = FloorPowerOfTwo (array.size) 分母 = 2のべき乗/16 numerator_step = array.size % denominator integer_step = floor (array.size / denominator) // 挿入ソート（一度に16 ～ 31個の項目）while (integer_step < array.size) 整数部分 = 分子 = 0 while (integer_part < array.size) // AとBの範囲を取得する 開始 = 整数部分 integer_part += integer_step 分子 += 分子ステップ （分子 ≥ 分母） 分子− = 分母 整数部分++ mid = 整数部分 integer_part += integer_step 分子 += 分子ステップ （分子 ≥ 分母） 分子 −= 分母 整数部分++ end = 整数部分 if (array[end − 1] < array[start]) Rotate (array, mid − start, [start, end)) else if (array[mid − 1] > array[mid]) Merge (array, A = [start, mid), B = [mid, end)) integer_step += integer_step numerator_step += numerator_step if (分子ステップ ≥ 分母) 分子ステップ −= 分母 整数ステップ++

マージ手順の各レベルに必要な 2 つの内部バッファは、Aサブ配列内の値の最初の2 √ AインスタンスをAの先頭に移動することによって作成されます。まず、 Aの要素を反復処理して必要な一意の値をカウントし、次に配列の回転を適用してそれらの一意の値を先頭に移動します。^{[ 6 ]} A に 2 つのバッファ (それぞれサイズ√ A ) を満たすのに十分な一意の値が含まれていない場合は、B を同様に使用できます。この場合、各値の最後のインスタンスをBの末尾に移動し、マージ中はBのその部分は含まれません。

while (integer_step < array.size) block_size = √ integer_step buffer_size = integer_step/block_size + 1 [それぞれサイズ「buffer_size」のバッファを2つ抽出する]

Bにも十分な数の固有値が含まれていない場合、可能な限り多くの固有値を抽出し、結果として得られるAブロックの数がバッファ用に抽出された固有項目の数以下になるように、AブロックとBブロックのサイズを調整します。この場合、使用されるバッファは1つだけで、2つ目のバッファは存在しません。

buffer_size = [見つかった一意の値の数] block_size = integer_step/buffer_size + 1 整数部分 = 分子 = 0 while (integer_part < array.size) [AとBの範囲を取得] [バッファで使用される範囲を含めないように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 の値と交換しますfor (index = 0, indexA = firstA.end + 1; indexA < blockA.end; indexA += block_size) Swap (array[buffer1.start + index], array[indexA]) インデックス++ lastA = firstA blockB = [B.start, B.start + minimum (block_size, |B|)] blockA.start += |firstA|

このようにAブロックを定義してタグ付けした後、最初の均等サイズのAブロックと次のBブロックを交換することで、AブロックはBブロック間を順に移動していきます。このプロセスは、タグ値が最小のAブロックの最初の値が、Aブロックと交換されたばかりのBブロックの最後の値以下になるまで繰り返されます。

その時点で、最小の A ブロック (タグ値が最小の A ブロック) がローリング A ブロックの先頭に移動され、タグ値は最初のバッファからの元の値で復元されます。これは、残りの A ブロックと一緒にローリングされなくなるため、ブロックを後方にドロップすると呼ばれます。次に、その A ブロックは、まず B に対してバイナリ サーチを使用して、A の最初の値がそのインデックスの B の値以下になるインデックスを見つけ、次にそのインデックスで A を B に回転させることによって、前の B ブロックに挿入されます。

 minA = blockA.start indexA = 0 while (true) // 前の B ブロックがあり、最小 A ブロックの最初の値が前の B ブロックの最後の値以下である場合、その最小 A ブロックを後ろに削除します。// または、B ブロックが残っていない場合は、残りの A ブロックを削除し続けます。if ((|lastB| > 0 and array[lastB.end - 1] ≥ array[minA]) or |blockB| = 0) // 前の B ブロックをどこで分割するかを判断し、分割時に回転させます B_split = BinaryFirst (array, array[minA], lastB) B_remaining = lastB.end - B_split // 最小の A ブロックをローリング A ブロックの先頭に交換しますBlockSwap (array, blockA.start, minA, block_size) // Aブロックの2番目の値を復元しますSwap (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 = [新しい最小 A ブロック] (下記参照) else if (|blockB| < block_size) // サイズが不均一な最後の B ブロックを// 回転を使用して残りの A ブロックの前に移動Rotate (array, blockB.start - blockA.start, [blockA.start, blockB.end)) lastB = [blockA.start, blockA.start + |blockB|) blockA.start += |blockB| blockA.end += |blockB| minA += |blockB| blockB.end = blockB.start else // 左端の A ブロックを次の B ブロックと交換して、一番左の A ブロックを最後まで移動します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 // これは最小値(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, B.end))

このステップで適用できる最適化の 1 つは、フローティング ホール テクニックです。^{[ 7 ]}最小の A ブロックが後ろにドロップされ、前の B ブロックに回転させる必要がある場合、その後、その内容がローカル マージ用の 2 番目の内部バッファにスワップされますが、A ブロックを事前にバッファにスワップして、そのバッファの内容が順序を保持する必要がないという事実を利用する方が高速です。したがって、2 番目のバッファ (ブロック スワップ前は A ブロックだった) を位置インデックスの前の B ブロックに回転させるのではなく、インデックス以降の B ブロックの値をバッファの最後の項目とブロック スワップするだけで済みます。

この場合の「浮遊する穴」とは、配列内を浮遊する第2内部バッファの内容を指し、項目が順序を保持する必要がないという意味で「穴」として機能します。

AブロックがBブロックに回転されると、前のAブロックはそれに続くB値とマージされ、2番目のバッファがスワップ領域として使用されます。最初の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、挿入数 = 0 (A_count < |A|かつB_count < |B|) の間、array[buffer.start + A_count] ≤ array[B.start + B_count] の場合、array[A.start + insert] と array[buffer.start + A_count]を交換します。 A_count++ それ以外の場合は 、配列[A.start + insert]と配列[B.start + B_count]を交換します。 B_count++ insert++ // バッファの残りの部分を配列の残りの部分とブロック交換しますBlockSwap (array, buffer.start + A_count, A.start + insert, |A| - A_count)

2 番目のバッファが存在しない場合は、Hwang と Lin アルゴリズムの回転ベースのバージョン^{[ 7 ] [ 8 ]} 、 Dudzinski と Dydek アルゴリズム^{[ 9 ]} 、または繰り返しバイナリ サーチと回転などの厳密にインプレース マージ操作を実行する必要があります。

MergeInPlace (array, A, B) while (|A| > 0 and |B| > 0) // A の最初の項目を挿入する必要がある B の最初の場所を見つける mid = BinaryFirst (array, array[A.start], B) // Aを回転させて所定の位置に配置 量 = 中間 - A.終了 回転（配列、量、[A.start、mid）） // 新しいAとBの範囲を計算する B = [mid, B.end] A = [A.start + amount, mid] A.start = BinaryLast (array, array[A.start], A)

最小のAブロックを削除し、前のAブロックとそれに続くB値をマージした後、配列内でまだ処理中のブロックの中から新しい最小のAブロックを見つける必要があります。これは、それらのAブロックに対して線形探索を実行し、タグ値を比較して最小値を見つけることで処理されます。

minA = blockA.start for (findA = minA + block_size; findA < blockA.end - 1; findA += block_size) if (array[findA + 1] < array[minA + 1]) minA = findA

残りのAブロックは、配列内を転がり続け、所定の位置に落とされて挿入されます。このプロセスは、すべてのAブロックが前のBブロックに落とされて回転されるまで繰り返されます。

最後のAブロックが後方にドロップされ、本来あるべきBに挿入されたら、それに続く残りのBの値とマージする必要があります。これで、その特定のAとBのサブ配列ペアのマージ処理が完了します。ただし、マージソートの現在のレベルにおいて、残りのAとBのサブ配列に対してこの処理を繰り返す必要があります。

なお、このレベルのマージソートでは、内部バッファはAとBのサブ配列のすべてのセットで再利用でき、再抽出や変更は一切必要ありません。

AとBのすべてのサブアレイがマージされた後も、1つまたは2つの内部バッファが残ります。最初の内部バッファはAブロックのタグ付けに使用され、その内容は以前と同じ順序で保持されていますが、2番目の内部バッファはマージのスワップ領域として使用された際に内容が再配置されている可能性があります。そのため、2番目のバッファの内容は挿入ソートなどの別のアルゴリズムを使用してソートする必要があります。その後、2つのバッファは、作成時とは逆のプロセスを使用して配列に再配置する必要があります。

これらの手順をボトムアップマージソートの各レベルで繰り返すと、ブロックソートが完了する。

ブロックソートの既知の実装例は以下のとおりです。

• クッツナーとキムによるC++での実装。^{[ 11 ]}
• Wikisortは、KutznerとKimの論文に基づいてMike McFaddenが実装したものです。^{[ 12 ]}
• ^{GrailSort（および書き換えられたHolyGrailSort）は、HuangとLangston（1992） [ 13 ]}に基づいてAndrey Astrelinが実装したもので、最終的には非常に類似したアルゴリズムを記述している^{[ 14 ] 。}
• Zigの標準ライブラリ^{[ 15 ] [ 16 ]}のデフォルトのソートアルゴリズムはバージョン0.2.0 ^{[ 17 ]}以降です。

^{ブロックソートは、}配列内の16 ～ 31 個の項目のグループに対して挿入ソートを実行することから始まります。挿入ソートはO ( n² )の操作なので、これはO (16² ^× n / 16)からO (31² ^× n / 31)までの範囲になります。定数係数を省略すると、 O ( n )になります。また、マージの各レベルが完了した後、2 番目の内部バッファに対しても挿入ソートを適用する必要があります。ただし、このバッファは制限されているため、${\displaystyle {\sqrt {A}}}$サイズ的には、${\displaystyle O({\sqrt {n}}^{2})}$操作も結局O ( n )になります。

次に、マージソートの各レベルごとに2つの内部バッファを抽出する必要があります。これは、AとBのサブ配列内の項目を反復処理し、値が変化するたびにカウンタをインクリメントし、十分な値が見つかったら、それらをAの先頭またはBの末尾に移動することで行います。最悪の場合、これは配列全体を検索してからでないと見つからないことになります。${\displaystyle {\sqrt {A}}}$連続しない一意の値、O ( n )回の比較が必要で、${\displaystyle {\sqrt {A}}}$回転${\displaystyle {\sqrt {A}}}$値。これは解決されます。${\displaystyle O(n+{\sqrt {n}}\times {\sqrt {n}})}$、またはO ( n )。

AまたはBサブアレイのいずれも含まれていない場合${\displaystyle {\sqrt {A}}}$内部バッファを作成するために一意の値がない場合、通常は最適ではないインプレースマージ操作が実行され、A を B に繰り返しバイナリ検索して回転させます。しかし、サブアレイ内に一意の値がないことがわかっているため、このステップで実行されるバイナリ検索と回転の数に厳しい制限が課せられます。${\displaystyle {\sqrt {A}}}$アイテムは${\displaystyle {\sqrt {A}}}$回数、またはO ( n )。各ブロックのサイズは、見つかった場合に小さくなるように調整されます。${\displaystyle {\sqrt {A}}}$一意の値だが2ではない${\displaystyle {\sqrt {A}}}$これにより、AブロックまたはBブロック内に含まれる一意の値の数をさらに制限します。

Aブロックのタグ付けが行われます${\displaystyle {\sqrt {A}}}$各Aサブアレイに対して回、その後Aブロックがロールスルーされ、Bブロックに挿入される。${\displaystyle {\sqrt {A}}}$回。ローカルマージは、標準マージと同じO ( n )の複雑さを維持しますが、値をコピーするのではなく交換する必要があるため、割り当て回数は多くなります。新しい最小値を見つけるための線形探索 A ブロックは、${\displaystyle {\sqrt {A}}}$ブロック${\displaystyle {\sqrt {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の値は少なくなります。