長い間、追加のメモリを使用しないようにマージして配列のソートを記述することは不可能であると考えていましたが、ランタイムはO（N * log（N））のままでした。 したがって、
karlicosがそのようなアルゴリズムの説明への
リンクを共有したとき、私は興味がありました。 ネットワーク上で検索した結果、人々はアルゴリズムについて知っていますが、誰もアルゴリズムに特に関心はなく、困難で効果がないと考えられています。 おそらく、それらはこのアルゴリズムのある種の「安定した」バージョンを意味しますが、それでも誰も不安定なものを必要としません。
しかし、私はまだ試してみることにしました。
線形マージ
アルゴリズムのアイデアは非常に簡単です。
O（N）比較と要素の交換で同じ配列の2つの順序付けられた部分をマージするだけです。 これは次のように行われます。
- 数S≈sqrt（N）を選択します
- 配列を長さSの K個に分割します。 私たちが触れるまで、どの部分にも落ちなかった残り
- 順序付けられたフラグメント間の境界が落ちたピースは、最後のピースで変更されます。 これがクリップボードになります。
- K-1を最初の要素の昇順で残りのピースをソートします。 ここでは、交換回数が線形のアルゴリズムを使用する必要があります。 最小要素を選択してソートするのが適切です。
- 2つの重要なことがわかります。 まず、長さAとBに 2桁のソートされたフラグメントがあり、長さがmin（A、B）以上のクリップボードがある場合、 A + B比較とA + Bを超えないでこれらのフラグメントをマージできます+分（A、B）の交換。 クリップボード内のアイテムの順序が変わる場合があります。 第二に、前のステップで取得した配列を（K-1）* S個の要素からソートする場合、各要素はS位置を超えて左に移動できません。 前の「ピース」の左側には決してありません。
- クリップボードを使用して、 [0..S-1]と[S、2 * S-1] 、次に[S、2 * S-1]と[2 * S、3 * S-1 ]のペアを連続してマージします]など 前の段落から、結果としてM = S *（K-1）要素のソートされた配列を取得することになります
- 元の配列の最後のR = NM要素（クリップボード+剰余）を任意のアルゴリズムで並べ替えます。 彼らはある種の二次アルゴリズムを推奨しています（アイデアを純粋にするため、再帰を避けるため）が、実用的な観点からは、ソートの再帰呼び出しは悪くありません。
- フラグメント[0..R-1]をクリップボードとして使用して、配列[R..NR-1]および[NR..N-1]のソート済みフラグメントをマージする
- アルゴリズムのエラーについては、前の段落と次の段落の接合部を調べています。 見つからない場合は、記事の最後で説明されています。
- クリップボードを並べ替えます：配列のR個のマイナー要素が含まれ、残り、並べ替え後に配置されます
説明は非常に長いですが、理解できます。 1つの合併の交換数は約
5 * Nで、比較の数は約
6 * Nです （残基の長さに依存します）。 完全なソートのために、これらの数値に
log（N）が掛けられ、ロットが取得されます。
ソートのためのアルゴリズム適応
私たちが簡単になり、アルゴリズムがより効率的に機能するように、次のことに注意してください。
- クリップボードとの大騒ぎとその後の配列とのマージは、配列に実際に空きスペースがなかった場合にのみ必要です。 長さAとBのフラグメントをマージし、それらの後にソートされていないスペースの少なくともSセルがある場合、配列を断片に分割し、ソートしてマージするだけで十分です。 これは、 S = A = Bの場合に特に効果的に機能します。
- 剰余の長さがゼロになり、ソートされたフラグメント間の境界が長さSの断片の境界に正確に収まるようにする必要があります。 これを実現する最も簡単な方法は、2の累乗に等しいSを選択し、 AとBをそれで除算することです。
- 配列の断片をソートするには、 （（A + B）/ S）2/2比較が必要です。 クリップボードの後続のソート-O（S *ログ（S））比較。 したがって、 sqrt（N）に近いSを選択する必要はありません;たとえば、 N / log（N）に増やすことができます 。
これらの考えを武器に、プログラムを作成しています（これまではint []型の配列のみ）。 最初に、2の累乗に等しい長さのフラグメントをソートおよびマージし、右側に空きスペースができるように厳密に左から右に移動します。 クリップボードに到達したら、未融合だがソートされたフラグメントをマージします。 クリップボード+残りを並べ替え、結果を残りの配列とマージし、新しく作成されたクリップボードを並べ替えます-配列が並べ替えられます。
約100行のアルゴリズムが判明しました。 真実はかさばると言われました。 効率はどうですか？
正直なところ、彼が標準のqsortに3回まで負けないことを望んでいました。 しかし、実際の条件（最大10
8の長さの配列）での比較では、qsortアルゴリズム
が比較回数で約10％を
上回り 、総操作時間で1.2から1.3倍の
パフォーマンスを示しました。 おそらくこれは、icmp関数（指定されたアドレスの2つの整数を比較する）がインラインで置換されるという事実によるものですが、挿入されるコードはかなりひどいものになります（チェックしました）。
一般的に、すべてが彼らが言ったほど悪くはありません。
しかし、アルゴリズムの説明にはどのようなエラーがありましたか？ 事実は、要素がクリップボードまたは残りの部分に到達した場合、ソート後に最初の
R位置の1つにあるはずであるため、最終的には配置されません。 修正するには、最後のマージでインデックス
Rを持つセル内の要素がどこに落ちたかを追跡し、この場所への最初のフラグメントに対して最後のソートを行う必要があります（その長さは
Rよりわずかに長い場合があります）。
UPD：アルゴリズムでは、ここで説明したように、「配列の断片の並べ替え」に関連するエラーがもう1つ発見されました。 ソース配列に多数の同一の要素がある場合、配列の同じフラグメントの異なる部分に同じ最初の要素がある場合があります。 また、ソート中にこれらのピースの順序に違反すると、配列全体のソート結果が不正確になる可能性があります。
この効果に対処するには、並べ替えの際に、ピースの最初の要素を比較し、同じ場合は最後の要素を比較する必要があります。 そして、これらの要素のペアで辞書順に並べ替えます。