マージソート

マージソート（ mergesortまたはmerge-sort ^{[ 2 ]}とも綴られる）は、効率的で汎用的な比較ベースのソートアルゴリズムです。マージソートのほとんどの実装は安定しており、入力と出力で等しい要素の相対的な順序が同じであることを意味します。マージソートは、1945 年にジョン・フォン・ノイマンによって発明された分割統治アルゴリズムです。 ^{[ 3 ]}ボトムアップマージソートの詳細な説明と分析は、 1948 年という早い時期にゴールドスタインとフォン・ノイマンによるレポートに登場しました。^{[ 4 ]}

概念的には、マージソートは次のように機能します。

1. ソートされていないリストを、それぞれ1つの要素を含むn個のサブリストに分割します（要素が1つのリストはソートされているとみなされます）。
2. サブリストを繰り返しマージして、ソート済みの新しいサブリストを作成し、最終的に1つのサブリストだけが残るようにします。これがソート済みのリストになります。

マージソートは、2つのサブリストが既にソートされている場合、それらのサブリストをマージしてソートする処理を線形時間で実行できるため、効率的である。

// 配列 a の一部を配列 b にコピーします (開始から終了 - 1 まで) void copyArray ( int [] a , int begin , int end , int [] b ) { for ( int k = begin ; k < end ; ++ k ) { b [ k ] = a [ k ] ; } }// 2 つのソートされた半分 (a から) を 1 つのソートされたラン (b へ) にマージしますvoid topDownMerge ( int [] a , int begin , int middle , int end , int [] b ) { int i = begin ; int j = middle ;// 2 つのソート済みランを b にマージするfor ( int k = begin ; k < end ; ++ k ) { if ( i < middle && ( j >= end || a [ i ] <= a [ j ] )) { b [ k ] = a [ i ] ; // 左側のランから要素を取得i ++ ; } else { b [ k ] = a [ j ] ; // 右側のランから要素を取得j ++ ; } } }// 配列 a を 2 つの半分に分割し、両方の半分を b にソートし、// ソートされた半分を a にマージします。void topDownSplitMerge ( int [] a , int begin , int end , int [] b ) { if ( end - begin <= 1 ) { return ; // 基本ケース: ラン サイズが 1 なので、既にソートされています}int middle = ( begin + end ) / 2 ; // 配列を分割する中間点を見つける// 左半分と右半分を再帰的にソートして b にしますtopDownSplitMerge ( b , begin , middle , a ); topDownSplitMerge ( b , middle , end , a );// ソートされた半分を再び結合するtopDownMerge ( b , begin , middle , end , a ); }void topDownMergeSort ( int [] a , int [] b , int n ) { // 最初に配列 a 全体を b にコピーするcopyArray ( a , 0 , n , b ); // 再帰的に配列 b を分割して a にマージするtopDownSplitMerge ( a , 0 , n , b ); }

// 配列 b を配列 a にコピーするvoid copyArray ( int [] b , int [] a , int n ) { for ( int i = 0 ; i < n ; i ++ ) { a [ i ] = b [ i ] ; } }// 左側のランは a[left : right-1] です。// 右側のランは a[right : end-1] です。void bottomUpMerge ( int [] a , int left , int right , int end , int [] b ) { int i = left ; int j = right ;// 左または右のランに要素が存在する間... for ( int k = left ; k < end ; ++ k ) { // 左ランの先頭が存在し、かつ右ランの先頭以下である場合。if ( i < right && ( j >= end || a [ i ] <= a [ j ] )) { b [ k ] = a [ i ] ; i = i + 1 ; } else { b [ k ] = a [ j ] ; j = j + 1 ; } } }void bottomUpMergeSort ( int [] a , int [] b , int n ) { // a の各 1 要素の連続は既に「ソート済み」です。// 配列全体がソートされるまで、長さ 2、4、8、16... のソート済み連続を順次作成します。for ( int width = 1 ; width < n ; width *= 2 ) { // 配列 a は長さ width の連続で満たされています。for ( int i = 0 ; i < n ; i = i + 2 * width ) { // 2 つの連続 a[i:i+width-1] と a[i+width:i+2*width-1] を b[] にマージします// または a[i:n-1] を b[] にコピーします (i+width >= n の場合) bottomUpMerge ( a , i , Math . min ( i + width , n ), Math . min ( i + 2 * width , n ), b ); } // これで、作業配列 b は長さ 2 * 幅の連続した要素で満たされます。// 次の反復処理のために、配列 b を配列 a にコピーします。// より効率的な実装では、a と b の役割を入れ替えます。copyArray ( b , a , n ); } }

function merge_sort( list m) is //基本ケース。定義により、要素が0個または1個のリストはソートされています。if length of m ≤ 1 then return m //再帰的なケース。まず、リストを前半と後半からなる同じサイズのサブリストに分割します 。 //これは、リストがインデックス 0 から始まることを前提としています。 var left := 空のリスト var right := 空のリスト m内のインデックスiを持つ各xについて、 i < (m の長さ)/2 の場合、 左側にxを追加する それ以外 右にxを加える //両方のサブリストを再帰的にソートします。 left := merge_sort(left) right := merge_sort(right) // 次に、ソートされたサブリストをマージします。 マージ(left, right)を返す

関数merge(left, right)は、 var result := 空のリストです。left が空ではなく、 right も空でない間、 first(left) ≤ first(right)ならば、 結果にfirst(left)を追加する left := rest(left) それ以外 結果にfirst(right)を追加する right := rest(right) // left または right のどちらかに要素が残っている可能性があります。それらを消費します。 // (以下のループのうち、実際に実行されるのは 1 つだけです。) while left is not empty do 結果にfirst(left)を追加する left := rest(left) right が空でない間、 結果にfirst(right)を追加する right := rest(right) 結果を返す

関数merge_sort( node head)は // リストが空の場合は返す head = nilの場合、 nil を 返します。 var node array[32]; 最初はすべて nil です 。 var node result var node next var int i 結果 := ヘッド // ノードを配列にマージする 結果がnilでない間、 next := result.next; result.next := nil for (i = 0; (i < 32) && (array[i] ≠ nil); i += 1) do result := merge(array[i], result) array[i] := nil // 配列の末尾を超えないようにする i = 32の場合 i -= 1 array[i] := result 結果 := 次の // 配列を単一のリストにマージする 結果 := nil for (i = 0; i < 32; i += 1) do result := merge(array[i], result) 結果を返す

mergeSort :: Ord a => [ a ] -> [ a ] mergeSort [] = [] mergeSort [ x ] = [ x ] mergeSort xs = merge ( mergeSort l , mergeSort r ) where ( l , r ) = splitAt ( length xs ` div ` 2 ) xsmerge :: Ord a => ([ a ], [ a ]) -> [ a ] merge ( [] , xs ) = xs merge ( xs , [] ) = xs merge ( x : xs , y : ys ) | x <= y = x : merge ( xs , y : ys ) | otherwise = y : merge ( x : xs , ys )

n個のオブジェクトをソートする場合、マージソートは平均および最悪の場合のパフォーマンスがO ( n  log n ) 回の比較となります。長さnのリストに対するマージソートの実行時間 (比較回数) がT ( n )である場合、アルゴリズムの定義 (元のリストの半分のサイズの 2 つのリストにアルゴリズムを適用し、結果として得られる 2 つのリストをマージするために実行された n 回のステップを追加する) から、漸化式 T ( n ) = 2 T ( n /2) + n が導かれます。 [ 5 ]閉じた形式は、分割統治^漸化式のマスター定理から導かれます。 

マージソートが最悪の場合に行う比較の回数は、ソート数で与えられます。これらの数は、( n  ⌈ lg n ⌉ − 2 ^{⌈lg n ⌉ + 1) と等しいか、わずかに小さい値であり、(} n lg n − n + 1) と ( n lg n + n + O(lg n ))の間にあります。^{[ 6 ]}マージソートの最良のケースでは、最悪のケースの約半分の反復回数で済みます。^{[ 7 ]}       

nが大きく、入力リストがランダムに順序付けられている場合、マージソートの期待される（平均）比較回数は、最悪の場合よりもα · n少なくなる。${\displaystyle \alpha =-1+\sum _{k=0}^{\infty }{\frac {1}{2^{k}+1}}\approx 0.2645.}$

最悪の場合、マージソートはクイックソートの平均の場合よりも約39%少ない比較回数を使用し、移動数で見ると、マージソートの最悪ケースの複雑さはO ( n  log n )であり、これはクイックソートの最良ケースの複雑さと同じです。^{[ 7 ]} 

マージソートは、ソート対象のデータが効率的に順次アクセスできる場合にのみ、一部のリストタイプにおいてクイックソートよりも効率的です。そのため、順次アクセスされるデータ構造が非常に一般的なLispなどの言語で広く用いられています。一部の（効率的な）クイックソートの実装とは異なり、マージソートは安定ソートです。

マージソートの最も一般的な実装では、インプレースソートは行われません。^{[ 8 ]}そのため、ソートされた出力を格納するために、入力のメモリサイズを割り当てる必要があります（ n /2 の追加スペースのみが必要なバリエーションについては、以下を参照）。

自然マージソートは、入力に自然に存在するラン（ソート済みシーケンス）を利用する点を除いて、ボトムアップマージソートと似ています。単調ランと双調ラン（交互に上/下）の両方を利用でき、リスト（または同等のテープやファイル）は便利なデータ構造です（ FIFOキューまたはLIFOスタックとして使用されます）。^{[ 9 ]}ボトムアップマージソートでは、開始点は各ランが1つのアイテムの長さであると想定します。実際には、ランダムな入力データには、たまたまソートされている短いランが多数存在します。典型的なケースでは、マージするランが少ないため、自然マージソートはそれほど多くのパスを必要としない場合があります。最良のケースでは、入力はすでにソートされている（つまり、1つのランである）ため、自然マージソートはデータを1回パスするだけで済みます。多くの実際的なケースでは、長い自然ランが存在するため、自然マージソートはTimsortの主要コンポーネントとして利用されます。例：

開始：3 4 2 1 7 5 8 9 0 6 選択ラン: (3 4)(2)(1 7)(5 8 9)(0 6) マージ: (2 3 4)(1 5 7 8 9)(0 6) マージ: (1 2 3 4 5 7 8 9)(0 6) マージ: (0 1 2 3 4 5 6 7 8 9)

正式には、自然マージソートはRuns最適であると言われ、${\displaystyle {\mathtt {実行数}}(L)}$は、${\displaystyle L}$マイナス1。

トーナメント置換選択ソートは、外部ソートアルゴリズムの初期実行データを収集するために使用されます。

一度に 2 つのブロックをマージする代わりに、ピンポン マージでは一度に 4 つのブロックをマージします。 4 つのソート済みブロックは同時に補助領域にマージされて 2 つのソート済みブロックになり、次に 2 つのソート済みブロックがメイン メモリにマージされます。 これにより、コピー操作が省略され、移動の総数が半分になります。 4 ブロック同時マージの初期のパブリック ドメイン実装は 2014 年に WikiSort によって行われ、その年の後半にこの方法は忍耐ソートの最適化として説明され、ピンポン マージと名付けられました。^{[ 10 ] [ 11 ]} Quadsort は 2020 年にこの方法を実装し、クワッド マージと名付けました。^{[ 12 ]}

配列に対してマージソートを実装する場合の欠点の1つは、O ( n )の作業メモリを必要とすることです。メモリ使用量を削減したり、マージソートを完全にインプレースで実行したりするためのいくつかの方法が提案されています。

• クロンロッド（1969）は、定数の追加スペースを使用するマージソートの代替バージョンを提案した。
• Katajainenらは、一定量の作業メモリを必要とするアルゴリズムを発表した。入力配列の 1 つの要素を保持するのに十分な記憶領域と、入力配列へのO (1)個のポインタを保持するための追加の領域である。彼らは小さな定数でO ( n log n )の時間制限を達成したが、そのアルゴリズムは安定していない。^{[ 13 ]}
• 標準的な（トップダウンまたはボトムアップ）マージソートと組み合わせてインプレースマージソートを生成できるインプレースマージアルゴリズムを作成する試みがいくつか行われてきました。この場合、「インプレース」の概念は「対数スタックスペースを取る」という意味に緩和できます。なぜなら、標準的なマージソートは、スタックの使用のためにその量のスペースを必要とするからです。Geffert らは、一定量のスクラッチスペースを使用して O ( n log n ) 時間でインプレースで安定したマージが可能であることを示しましたが、彼らのアルゴリズムは複雑で定数係数が大きく、長さnとmの配列をマージするには5 n + 12 m + o ( m )回の移動が必要になる可能性があります。^{[ 14 ]}この定数係数が大きく複雑なインプレースアルゴリズムは、より単純で理解しやすくなりました。Bing-Chao Huang と Michael A. Langston ^{[ 15 ]}は、固定量の追加スペースを使用してソート済みリストをマージする、単純な線形時間アルゴリズムの実用的なインプレースマージを発表しました。彼らは両方とも Kronrod らの研究を利用しています。線形時間と定数の追加スペースでマージします。このアルゴリズムは、O ( n )の一時的な追加メモリセルを自由に利用できる標準的なマージソートアルゴリズムよりも平均時間がわずかに長く、2 倍未満です。このアルゴリズムは実際にははるかに高速ですが、一部のリストでは不安定です。しかし、同様の概念を使用して、この問題を解決することができました。他のインプレースアルゴリズムには、合計でO (( n + m ) log( n + m ))時間を要し、安定している SymMerge があります。 ^{[ 16 ]}このようなアルゴリズムをマージソートに組み込むと、その複雑さは非線形算術的、しかし依然として準線形であるO ( n (log n ) ² )に増加します。
• 外部ソートの多くのアプリケーションでは、マージソートと呼ばれる形式が用いられます。これは、入力データをより多くのサブリストに分割するもので、理想的には、それらをマージしても現在処理中のページセットがメインメモリに収まるような数に分割されます。
• 現代的で安定した線形かつインプレースなマージ方式のバリアントとして、ブロックマージソートがある。これは、スワップ領域として使用する一意の値のセクションを作成する。
• バイナリサーチと回転を用いることで、空間オーバーヘッドをO ( √n )に削減できる。^{[ 17 ]}この方法はC++ STLライブラリとquadsortで採用されている。^{[ 12 ]}
• 複数のリストへのコピーを減らす代替手段として、各キー（mの要素はキーと呼ばれます）に新しい情報フィールドを関連付ける方法があります。このフィールドは、ソートされたリスト（キーとその関連情報はレコードと呼ばれます）内でキーと関連情報をリンクするために使用されます。その後、リンク値を変更することでソートされたリストのマージが行われます。レコードを移動する必要は一切ありません。リンクのみを含むフィールドは、一般的にレコード全体よりも小さいため、使用するスペースも少なくなります。これはマージソートに限らず、標準的なソート手法です。
• スペースオーバーヘッドをn /2 に削減する簡単な方法は、 leftとright を結合構造として保持し、 mの左側部分のみを一時領域にコピーし、マージルーチンにマージされた出力をmに配置するように指示することです。このバージョンでは、一時領域をマージルーチンの外で割り当てる方が、割り当てが 1 回で済むため好ましいです。また、 return resultステートメントの直前の最後の 2 行 (上記の擬似コードの関数merge ) が不要になるため、前述の過剰なコピーも軽減されます。

外部マージソートは、ソート対象のデータが大きすぎてメモリに収まらない場合に、ディスクドライブやテープドライブを使用して実行するのが実用的です。外部ソートでは、ディスクドライブを使用したマージソートの実装方法について説明します。一般的なテープドライブソートでは、4台のテープドライブを使用します。入出力はすべてシーケンシャルです（各パスの最後に巻き戻しを行う場合を除く）。最小限の実装であれば、2つのレコードバッファと少数のプログラム変数だけで済みます。

4つのテープドライブをA、B、C、Dと名付け、Aに元のデータが格納され、レコードバッファを2つだけ使用すると、このアルゴリズムはボトムアップ実装に似ており、メモリ内の配列の代わりにテープドライブのペアを使用します。基本的なアルゴリズムは次のように説明できます。

1. Aからレコードのペアをマージし、2つのレコードからなるサブリストを交互にCとDに書き込む。
2. CとDからそれぞれ2つのレコードからなるサブリストをマージして4つのレコードからなるサブリストを作成し、それらを交互にAとBに書き込む。
3. AとBの4レコードのサブリストをマージして8レコードのサブリストを作成し、これをCとDに交互に書き込む。
4. すべてのデータがソートされたリストが1つできるまで、これを繰り返します。これはlog ₂ ( n )回のパスで完了します。

非常に短いランから始める代わりに、通常はハイブリッド アルゴリズムが使用されます。このアルゴリズムでは、最初のパスで多数のレコードをメモリに読み込み、内部ソートを実行して長いランを作成し、それらの長いランを出力セットに分配します。このステップにより、多くの初期パスが回避されます。たとえば、1024 レコードの内部ソートでは、9 つ​​のパスが節約されます。内部ソートは、このような利点があるため、多くの場合大規模になります。実際、利用可能な内部メモリよりも長い初期ランを作成できる手法があります。その 1 つは、Knuth の「snowplow」（バイナリ最小ヒープに基づく）で、使用されるメモリ サイズの 2 倍の長さのランを（平均して）生成します。^{[ 18 ]}

多少のオーバーヘッドはあるものの、上記のアルゴリズムは3本のテープを使用するように変更できます。2つのキュー、スタックとキュー、または3つのスタックを使用することで、 O ( n log n )の実行時間も実現できます。反対に、k > 2本のテープ（およびメモリ内のO ( k )個のアイテム）を使用すると、 k/2方向マージを使用することで、テープ操作の数をO (log k )倍に減らすことができます。

テープ（およびディスク）ドライブの使用を最適化する、より高度なマージソートは、ポリフェーズマージソートです。

現代のコンピュータでは、マルチレベルのメモリ階層が使用されるため、参照の局所性がソフトウェア最適化において極めて重要になることがあります。マシンのメモリキャッシュへのページの出し入れを最小限に抑えるように操作が特別に選択された、キャッシュ対応バージョンのマージソートアルゴリズムが提案されています。たとえば、タイルマージソートアルゴリズムは、CPUのキャッシュに収まるデータ項目の数であるSのサイズのサブアレイに達した時点で、サブアレイの分割を停止します。これらのサブアレイはそれぞれ、挿入ソート、その後、通常の再帰的な方法で通常のマージソートが実行されます。このアルゴリズムは、キャッシュ最適化の恩恵を受けるマシンで優れたパフォーマンスを発揮することが実証されています。（LaMarca & Ladner 1997）

マージソートは分割統治法を用いるため、並列処理に適しています。長年にわたり、このアルゴリズムのさまざまな並列版が開発されてきました。並列マージソートアルゴリズムの中には、逐次的なトップダウンマージアルゴリズムと密接に関連しているものもあれば、一般的な構造が異なり、Kウェイマージ方式を用いるものもあります。

//配列 A の要素 lo から hi (排他的) をソートします。アルゴリズムmergesort(A, lo, hi)は、lo+1 < hiの場合、 // 2 つ以上の要素です。 中間値 := ⌊(lo + hi) / 2⌋ fork mergesort(A, lo, mid) mergesort(A, mid, hi) join merge(A, lo, mid, hi)

/** * A: 入力配列 * B: 出力配列 * lo: 下限値 * hi: 上限 * オフ: オフセット */ アルゴリズムparallelMergesort(A, lo, hi, B, off)は len := hi - lo + 1 len == 1の場合、 B[off] := A[lo] とし、そうでない場合は、T[1..len] を新しい配列とする。 中間値 := ⌊(lo + hi) / 2⌋ mid' := mid - lo + 1 fork parallelMergesort(A, lo, mid, T, 1) parallelMergesort(A, mid + 1, hi, T, mid' + 1) join parallelMerge(T, 1, mid', mid' + 1, len, B, off)

並列マルチウェイマージソート

マージソートアルゴリズムをバイナリマージ方式に限定するのは恣意的であるように思われる。なぜなら、通常 p > 2 個のプロセッサが利用可能だからである。より良いアプローチは、バイナリマージの一般化であるK ウェイマージ方式を使用することかもしれない。${\displaystyle k}$ソートされたシーケンスがマージされます。このマージバリアントは、 PRAM上のソートアルゴリズムを説明するのに適しています。^{[ 21 ] [ 22 ]}

基本的な考え方

ソートされていないシーケンスが与えられた${\displaystyle n}$要素、目標はシーケンスをソートすることです${\displaystyle p}$利用可能なプロセッサ。これらの要素はすべてのプロセッサに均等に分散され、逐次ソートアルゴリズムを使用してローカルでソートされます。したがって、シーケンスはソートされたシーケンスで構成されます。${\displaystyle S_{1},...,S_{p}}$長さ${\textstyle \lceil {\frac {n}{p}}\rceil }$簡略化のため、${\displaystyle n}$倍数である${\displaystyle p}$、 となることによって${\textstyle \left\vert S_{i}\right\vert ={\frac {n}{p}}}$のために${\displaystyle i=1,...,p}$。

これらのシーケンスは、マルチシーケンス選択/スプリッター選択を実行するために使用されます。${\displaystyle j=1,...,p}$アルゴリズムはスプリッター要素を決定します${\displaystyle v_{j}}$世界ランキング${\textstyle k=j{\frac {n}{p}}}$すると、対応する位置は${\displaystyle v_{1},...,v_{p}}$各シーケンスにおいて${\displaystyle S_{i}}$バイナリサーチで決定され、したがって${\displaystyle S_{i}}$さらに分割され${\displaystyle p}$部分列${\displaystyle S_{i,1},...,S_{i,p}}$と${\textstyle S_{i,j}:=\{x\in S_{i}|rank(v_{j-1})<rank(x)\leq rank(v_{j})\}}$。

さらに、${\displaystyle S_{1,i},...,S_{p,i}}$プロセッサに割り当てられる${\displaystyle i}$、ランク間のすべての要素を意味します${\textstyle (i-1){\frac {n}{p}}}$そしてランク${\textstyle i{\frac {n}{p}}}$すべてに分布している${\displaystyle S_{i}}$したがって、各プロセッサはソートされたシーケンスのシーケンスを受け取ります。ランク${\displaystyle k}$スプリッター要素の${\displaystyle v_{i}}$世界的に選ばれ、2つの重要な特性を提供します。一方では、${\displaystyle k}$各プロセッサが引き続き動作できるように選択されました${\textstyle n/p}$割り当て後の要素。アルゴリズムは完全に負荷分散されています。一方、プロセッサ上のすべての要素${\displaystyle i}$プロセッサ上のすべての要素以下である${\displaystyle i+1}$したがって、各プロセッサはローカルでpウェイマージを実行し、そのサブシーケンスからソートされたシーケンスを取得します。2番目の特性により、それ以上のpウェイマージを実行する必要はなく、結果をプロセッサ番号の順序で組み合わせるだけで済みます。

マルチシーケンス選択

最も単純な形では、${\displaystyle p}$ソートされたシーケンス${\displaystyle S_{1},...,S_{p}}$均等に分布${\displaystyle p}$プロセッサとランク${\displaystyle k}$タスクは要素を見つけることです${\displaystyle x}$世界ランキング${\displaystyle k}$シーケンスの和集合において。したがって、これを使用して各を分割することができます。${\displaystyle S_{i}}$スプリッターインデックスで2つの部分に分割${\displaystyle l_{i}}$下部には、より小さい要素のみが含まれる${\displaystyle x}$より大きい要素${\displaystyle x}$上部に位置しています。

提示された逐次アルゴリズムは、各シーケンス内の分割のインデックスを返します。たとえば、インデックス${\displaystyle l_{i}}$シーケンスで${\displaystyle S_{i}}$そのため${\displaystyle S_{i}[l_{i}]}$世界ランキングは以下${\displaystyle k}$そして${\displaystyle \mathrm {rank} \left(S_{i}[l_{i}+1]\right)\geq k}$[ ^{23 ]​}

アルゴリズムmsSelect(S : ソートされたシーケンスの配列 [S_1,..,S_p], k : int)は i = 1からpまで実行されます (l_i, r_i) = (0, |S_i|-1) i が存在する間: l_i < r_iを実行する // S_j[l_j]、...、S_j[r_j] からピボット要素を選択し、j を一様にランダムに選択する v := pickPivot(S, l, r) i = 1からpまで繰り返す m_i = binarySearch(v, S_i[l_i, r_i]) // 順次 もしm_1 + ... + m_p >= kならば// m_1 + ... + m_p は v のグローバルランクである r := m // ベクトルの代入 それ以外 l := m lを返す

複雑性分析にはPRAMモデルが選択されます。データが全体に均等に分散されている場合${\displaystyle p}$バイナリサーチメソッドのp分割実行の実行時間は${\displaystyle {\mathcal {O}}\left(p\log \left(n/p\right)\right)}$予想される再帰深度は${\displaystyle {\mathcal {O}}\left(\log \left(\textstyle \sum _{i}|S_{i}|\right)\right)={\mathcal {O}}(\log(n))}$通常のクイックセレクトと同様です。したがって、全体の予想実行時間は${\displaystyle {\mathcal {O}}\left(p\log(n/p)\log(n)\right)}$。

並列マルチウェイマージソートに適用する場合、このアルゴリズムは、ランクのすべてのスプリッター要素が並列に呼び出されるようにする必要があります。${\textstyle i{\frac {n}{p}}}$のために${\displaystyle i=1,..,p}$これらは同時に見つかります。これらの分割要素は、各シーケンスを分割するために使用できます。${\displaystyle p}$部品の総実行時間は同じで、${\displaystyle {\mathcal {O}}\left(p\,\log(n/p)\log(n)\right)}$。

擬似コード

以下に、並列マルチウェイマージソートアルゴリズムの完全な擬似コードを示す。マルチシーケンス選択の前後にバリア同期が行われ、各プロセッサが分割要素とシーケンス分割を適切に決定できるものと仮定する。

/** * d: ソートされていない要素の配列 * n: 要素数 * p: プロセッサ数 * ソートされた配列を返します */ アルゴリズムparallelMultiwayMergesort(d : Array, n : int, p : int)は、 o := new Array[0, n] // 出力配列 、 i = 1からpまで並列に実行 // 各プロセッサを並列に 実行 S_i := d[(i-1) * n/p, i * n/p] // 長さ n/p のシーケンス sort(S_i) // ローカルでソート 同期 v_i := msSelect([S_1,...,S_p], i * n/p) // グローバルランク i * n/p の要素 同期 (S_i,1, ..., S_i,p) := sequence_partitioning(si, v_1, ..., v_p) // s_i を部分列に分割する o[(i-1) * n/p, i * n/p] := kWayMerge(s_1,i, ..., s_p,i) // マージして出力配列に代入 戻る​

分析

まず、各プロセッサは割り当てられた${\displaystyle n/p}$要素をローカルでソートアルゴリズムを使用して複雑度で処理します${\displaystyle {\mathcal {O}}\left(n/p\;\log(n/p)\right)}$その後、スプリッタ要素を時間的に計算する必要がある。${\displaystyle {\mathcal {O}}\left(p\,\log(n/p)\log(n)\right)}$最後に、各グループの${\displaystyle p}$分割は各プロセッサによって並列にマージされ、実行時間は${\displaystyle {\mathcal {O}}(\log(p)\;n/p)}$逐次pウェイマージアルゴリズムを使用する。したがって、全体の実行時間は次式で与えられる。

${\displaystyle {\mathcal {O}}\left({\frac {n}{p}}\log \left({\frac {n}{p}}\right)+p\log \left({\frac {n}{p}}\right)\log(n)+{\frac {n}{p}}\log(p)\right)}$。

実践的な適応と応用

マルチウェイマージソートアルゴリズムは、多数のプロセッサを使用できる高い並列化能力により、非常にスケーラブルです。このため、このアルゴリズムは、コンピュータクラスタで処理されるような大量のデータをソートするのに適した候補となります。また、このようなシステムでは通常メモリが制限要因にならないため、マージソートの空間計算量の欠点は無視できます。ただし、このようなシステムでは、 PRAM上でモデル化する際に考慮されない他の要因が重要になります。ここで、次の側面を考慮する必要があります。メモリ階層、データがプロセッサのキャッシュに収まらない場合、またはプロセッサ間でデータを交換するための通信オーバーヘッド。これは、共有メモリを介してデータにアクセスできなくなった場合にボトルネックになる可能性があります。

Sandersらは論文で、マルチレベルマルチウェイマージソートのためのバルク同期並列アルゴリズムを発表しており、${\displaystyle p}$プロセッサを${\displaystyle r}$規模のグループ${\displaystyle p'}$すべてのプロセッサは最初にローカルでソートします。単一レベルのマルチウェイマージソートとは異なり、これらのシーケンスは次に分割されます。${\displaystyle r}$部品は適切なプロセッサグループに割り当てられます。これらの手順は、それらのグループ内で再帰的に繰り返されます。これにより通信が削減され、特に多数の小さなメッセージによる問題が回避されます。基盤となる実際のネットワークの階層構造を使用して、プロセッサグループ（ラック、クラスタなど）を定義できます。^{[ 22 ]}

ヒープソートはマージソートと同じ時間制限を持ちますが、マージソートのΘ( n )の代わりにΘ(1)の補助空間しか必要としません。一般的な最新のアーキテクチャでは、効率的なクイックソートの実装は、RAMベースの配列のソートにおいて、一般的にマージソートよりも優れたパフォーマンスを発揮します。^{[ 27 ]}クイックソートは、ソートするデータのサイズが小さい場合に好まれます。クイックソートの空間計算量はO(log n )であるため、マージソート(空間計算量はO(n))よりもキャッシュの局所性をより効果的に活用できます。^{[ 27 ]}一方、マージソートは安定ソートであり、アクセスが遅いシーケンシャルメディアの処理に効率的です。マージソートは、リンクリストのソートに最適な選択肢となることがよくあります。この場合、マージソートをΘ(1)の追加空間のみを必要とするように実装することは比較的容易であり、リンクリストのランダムアクセス性能が遅いため、他のアルゴリズム(クイックソートなど)のパフォーマンスが低下し、他のアルゴリズム(ヒープソートなど)は完全に不可能になります。

Perl 5.8以降では、マージソートがデフォルトのソートアルゴリズムとなっています (以前のバージョンの Perl ではクイックソートでした)。^{[ 28 ]} Javaでは、Arrays.sort()メソッドはデータ型に応じてマージソートまたは調整されたクイックソートを使用し、実装効率のために、ソート対象の配列要素が 7 つ未満の場合は挿入ソートに切り替えます。 ^{[ 29 ]} Linuxカーネルは、リンク リストにマージソートを使用しています。^{[ 30 ]}

Timsort は、マージソートと挿入ソートの調整されたハイブリッドであり、Java やAndroidプラットフォーム^{[ 31 ]}を含むさまざまなソフトウェア プラットフォームや言語で使用されており、 Pythonではバージョン 2.3 以降使用されています。バージョン 3.11 以降、Timsort のマージ ポリシーはPowersortに更新されました。^{[ 32 ]}

• トーマス・H・コーメン;チャールズ・E・ライザーソン;ロナルド・L・リベスト;スタイン、クリフォード(2009) [1990]。アルゴリズム入門(第 3 版)。 MIT プレスとマグロウヒル。ISBN 0-262-03384-4。
• Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). "Practical in-place mergesort" . Nordic Journal of Computing . 3 (1): 27–40 . CiteSeerX 10.1.1.22.8523 . ISSN 1236-6064 . 2011年8月7日のオリジナルからアーカイブ済み。 2009年4月4日取得。  また、実用的なインプレースマージソートも。
• クヌース、ドナルド（1998）。「セクション 5.2.4：マージによるソート」。『ソートと検索』。『コンピュータプログラミングの技法』第 3 巻 （第 2 版）。アディソン・ウェスリー。158 ～ 168ページ。ISBN  0-201-89685-0。
• Kronrod, MA (1969). 「演算体を用いない最適順序付けアルゴリズム」.ソビエト数学 - Doklady . 10 : 744.
• LaMarca, A.; Ladner, RE (1997). 「キャッシュがソートのパフォーマンスに与える影響」。第8 回 ACM-SIAM 離散アルゴリズムシンポジウム (SODA97)論文集: 370–379。CiteSeerX 10.1.1.31.1153 。 
• Skiena, Steven S. (2008). "4.5: マージソート: 分割統治法によるソート".アルゴリズム設計マニュアル(第 2 版). Springer. pp. 120–125 . ISBN  978-1-84800-069-8。
• サン・マイクロシステムズ。「配列API（Java SE 6）」 。 2007年11月19日取得。
• Oracle Corp. 「配列（Java SE 10 & JDK 10）」 。 2018年7月23日取得。

• アニメーションによるソートアルゴリズム：マージソート（ Wayback Machineアーカイブ、2015年3月6日） – グラフィカルなデモンストレーション
• オープンデータ構造 - セクション 11.1.1 - マージソート、パット・モリン
• マージソートアルゴリズムを実装するC言語プログラム
• Javaを使用したマージソートコード
• マージソート用のC++プログラム