マージソート

マージソート

マージソートの例。まず、リストを最小単位（1要素）に分割し、各要素を隣接するリストと比較して、隣接する2つのリストをソートしてマージします。最後に、すべての要素がソートされ、マージされます。
クラス	ソートアルゴリズム
データ構造	配列
最悪の場合の パフォーマンス	${\displaystyle O(n\log n)}$
最高の パフォーマンス	${\displaystyle \Omega (n\log n)}$典型的な、 自然な変種${\displaystyle \オメガ (n)}$
平均的 なパフォーマンス	${\displaystyle \Theta (n\log n)}$
最悪の場合の 空間複雑度	${\displaystyle O(n)}$補助リスト付き合計、補助リスト付きリンクリスト[1]${\displaystyle O(n)}$${\displaystyle O(1)}$

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

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

1. ソートされていないリストを、それぞれ 1 つの要素を含むn個のサブリストに分割します (1 つの要素のリストはソートされていると見なされます)。
2. サブリストを繰り返しマージして、サブリストが 1 つだけ残るまで、新しいソートされたサブリストを作成します。これがソートされたリストになります。

インデックスを使用してトップダウン マージ ソート アルゴリズムを実行するC のようなコードの例。このアルゴリズムでは、リスト (この例ではrunsと呼ばれます) をサブリスト サイズが 1 になるまでサブリストに再帰的に分割し、それらのサブリストをマージしてソートされたリストを生成します。コピー バック手順は、再帰の各レベルでマージの方向を交互にすることで回避されます (最初の 1 回限りのコピーは除きます。これも回避できます)。

簡単な例として、2 つの要素を持つ配列を考えてみましょう。要素は B[] にコピーされ、その後 A[] にマージされます。要素が 4 つある場合、再帰レベルの最下部に到達すると、A[] からの 1 つの要素の実行が B[] にマージされ、次に再帰の次の上位レベルで、それらの 2 つの要素の実行が A[] にマージされます。このパターンは、再帰の各レベルで継続されます。

// 配列 A[] にはソートする項目があり、配列 B[] は作業配列です。
void TopDownMergeSort ( A [], B [], n ) { CopyArray ( A , 0 , n , B ); // A[] を B[] に 1 回コピーTopDownSplitMerge ( A , 0 , n , B ); // B[] から A[] にデータをソート}   

                  
          


// A[] を 2 つの実行に分割し、両方の実行を B[] にソートし、両方の実行を B[] から A[] にマージします
// iBegin は包括的ですが、iEnd は排他的です (A[iEnd] はセット内にありません)。
void TopDownSplitMerge ( B [], iBegin , iEnd , A []) { if ( iEnd - iBegin <= 1 ) // 実行サイズが 1 の場合return ; // ソート済みと見なします// 1 項目より長い実行を半分に分割しますiMiddle = ( iEnd + iBegin ) / 2 ; // iMiddle = 中間点// 配列 A[] の両方の実行を再帰的にソートして B[] に格納しますTopDownSplitMerge ( A , iBegin , iMiddle , B ); // 左側の実行をソートしますTopDownSplitMerge ( A , iMiddle , iEnd , B ); // 右側の実行をソートします// 結果の実行を配列 B[] から A[] にマージしますTopDownMerge ( B 、iBegin 、iMiddle 、iEnd 、A ); }    

                              
                                         
    
                        
    
          
            
    
        



// 左ソース半分は A[ iBegin : iMiddle-1] です。//右ソース半分は A[iMiddle:iEnd-1 ] です。//
結果は B[ iBegin:iEnd-1 ] です。void 
TopDownMerge ( B [], iBegin , iMiddle , iEnd , A []) { i = iBegin , j = iMiddle ; // 左または右のランに要素がある間... for ( k = iBegin ; k < iEnd ; k ++ ) { // 左ラン ヘッドが存在し、それが既存の右ラン ヘッド以下である場合。if ( i < iMiddle && ( j >= iEnd || A [ i ] <= A [ j ])) { B [ k ] = A [ i ]; i = i + 1 ; } else { B [ k ] = A [ j ]; j = j + 1 ; } } }     

         
 
    
            
        
                    
              
                
          
              
                
        
    


void CopyArray ( A [], iBegin , iEnd , B []) { for ( k = iBegin ; k < iEnd ; k ++ ) B [ k ] = A [ k ]; }    

           
          

配列全体のソートはTopDownMergeSort(A, B, length(A))によって実行されます。

リストをサイズ 1 のn個のサブリスト (この例ではrunsと呼ばれます)の配列として扱い、2 つのバッファー間でサブリストを繰り返しマージするボトムアップ マージ ソート アルゴリズムのインデックスを使用する C のようなコードの例:

// 配列 A[] にはソートする項目があります。配列 B[] は作業配列です。
void BottomUpMergeSort ( A [], B [], n ) { // A 内の各 1 要素のランはすでに「ソート済み」です。// 配列全体がソートされるまで、長さ 2、4、8、16... のソート済みランを順次長くします。for ( width = 1 ; width < n ; width = 2 * width ) { // 配列 A は長さ width のランでいっぱいです。for ( 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[] にコピーします ( if (i+width >= n) ) BottomUpMerge ( A , i , min ( i + width , n ), min ( i + 2 * width , n ), B ); } // これで、配列 B は長さ 2*width の実行でいっぱいになります。// 次の反復処理のために、配列 B を配列 A にコピーします。// より効率的な実装では、A と B の役割を入れ替えます。CopyArray ( B , A , n ); // これで、配列 A は長さ 2*width の実行でいっぱいになります。} }   

    
    
               
    
        
                     
        
            
            
                  
        
        
        
        
          
        
    


// 左ランは A[iLeft :iRight-1] です。//
右ランは A[iRight:iEnd-1 ] です。void 
BottomUpMerge ( A [], iLeft , iRight , iEnd , B []) { i = iLeft , j = iRight ; // 左または右ランに要素がある間... for ( k = iLeft ; k < iEnd ; k ++ ) { // 左ランのヘッドが存在し、それが既存の右ランのヘッド以下である場合。if ( i < iRight && ( j >= iEnd || A [ i ] <= A [ j ])) { B [ k ] = A [ i ]; i = i + 1 ; } else { B [ k ] = A [ j ]; j = j + 1 ; } } }     

         
    
            
        
                    
              
                
          
              
                    
        
     


void CopyArray ( B [], A [], n ) { for ( i = 0 ; i < n ; i ++ ) A [ i ] = B [ i ]; }   

           
          

入力リストを、サブリストが簡単にソートされるまで再帰的に小さなサブリストに分割し、呼び出しチェーンを上に戻しながらサブリストをマージするトップダウン マージ ソート アルゴリズムの 疑似コード。

function merge_sort( list m)は
    //基本ケースです。定義により、0 個または 1 個の要素を持つリストがソートされます。m
    の長さが 1 未満の場合は
        m を返します。

    //再帰的なケース。まず、リストを、リストの前半と後半からなる同じサイズのサブリストに分割します
    。
    //これは、リストがインデックス 0 から始まることを前提としています。 var left := 空のリスト
    var right := 空のリスト
    m内のインデックスiを持つ各xに対して、i < (m の長さ)/2 の場合、 do if i < (m の長さ)/2 then
    
        
            左にxを追加
        それ以外
            右にxを追加

    //両方のサブリストを再帰的にソートします。
    左 := merge_sort(左)
    右 := merge_sort(右)

    // 次に、ソートされたサブリストを結合します。
    マージを返す(左、右)

この例では、マージ関数は左と右のサブリストをマージします。

関数merge(left, right) はvar result := 空のリストです
    

    左が空でなく右が空でない場合、 first(left) ≤ first(right)であれ
        ば
            結果に最初(左)を追加
            左 := 残り(左)
        それ以外
            結果に最初(右)を追加
            右 := 残り(右)

    // left または right のどちらかに要素が残っている可能性があります。それらを消費します。 
    // (次のループのうち実際に実行されるのは 1 つだけです。)
     left が空でない場合は、
        結果に最初(左)を追加
        左 := 残り(左)
    右が空でない間は
        結果に最初(右)を追加
        右 := 残り(右)
    結果
を返す

ノードへの参照の小さな固定サイズの配列を使用するボトムアップ マージ ソート アルゴリズムの疑似コードです。array[i] は、サイズ 2 ⁱのリストへの参照またはnilです。nodeはノードへの参照またはポインタです。merge() 関数は、トップダウン マージ リストの例で示したものと似ており、既にソートされた 2 つのリストをマージし、空のリストを処理します。この場合、merge() は入力パラメータと戻り値に node を使用します。

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

Haskellのような擬似コード。関数型プログラミングの構成要素とアイデアを使用して、このような言語でマージソートを実装する方法を示します。

merge_sort :: [ a ] -> [ a ] merge_sort ( [] ) = [] merge_sort ([ x ]) = [ x ] merge_sort ( xs ) = merge ( merge_sort ( left ), merge_sort ( right )) where ( left , right ) = split ( xs , length ( xs ) / 2 ) merge :: ([ a ], [ a ]) -> [ a ] merge ( [] , xs ) = xs merge ( xs , [] ) = xs merge ( x : xs , y : ys ) | if x ≤ y = x : merge ( xs , y : ys ) | else = y : merge ( x : xs , ys )    
   
  
    
         
  
     
   
   
      
              
               

n 個のオブジェクトをソートする場合、マージソートの平均および最悪のパフォーマンスはO ( n  log  n ) 回の比較です。長さnのリストに対するマージソートの実行時間 (比較回数)がT ( n ) の場合、アルゴリズムの定義から再帰関係 T ( n ) = 2 T ( n /2) + nが導かれます (アルゴリズムを元のリストの半分のサイズの 2 つのリストに適用し、結果として得られる 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)

正式には、自然なマージソートは、の実行数から1 を引いた値である実行最適であると言われています。 ${\displaystyle {\mathtt {実行数}}(L)}$${\displaystyle L}$

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

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

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

• Kronrod (1969) は、一定の追加スペースを使用するマージソートの代替バージョンを提案しました。
• カタヤイネンらは、一定量の作業メモリを必要とするアルゴリズムを提示している。これは、入力配列の1つの要素を保持するのに十分な記憶領域と、入力配列へのO(1)個のポインタを保持するための追加の領域である。彼らは小さな定数でO ( nlogn )の時間制限を達成したが、そのアルゴリズムは安定していない。^[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 ( logn ) 2 ⁾になります。
• 外部ソートの多くのアプリケーションでは、入力がより多くのサブリストに分割されるマージソートの形式が使用されます。理想的には、サブリストをマージしても、現在処理されているページのセットがメインメモリに収まる数に分割されます。
• 最新の安定した線形インプレース マージ バリアントは、スワップ領域として使用する一意の値のセクションを作成するブロック マージ ソートです。
• バイナリ検索と回転を使用することで、空間オーバーヘッドをO (√n )に削減できます。 ^[17]この方法は、C++ STLライブラリとクワッドソートで採用されています。^[12]
• 複数のリストへのコピーを減らす別の方法として、各キーに新しい情報フィールドを関連付ける方法があります ( m内の要素はキーと呼ばれます)。このフィールドは、ソートされたリスト内でキーと関連情報をリンクするために使用されます (キーとその関連情報はレコードと呼ばれます)。次に、ソートされたリストのマージは、リンク値を変更することによって進行します。レコードを移動する必要はありません。リンクのみを含むフィールドは、通常、レコード全体よりも小さいため、使用されるスペースも少なくなります。これは、マージ ソートに限定されない標準的なソート手法です。
• スペースのオーバーヘッドをn /2に減らす簡単な方法は、 leftとright を結合構造として維持し、 mの左側部分のみを一時スペースにコピーし、マージルーチンにマージされた出力をmに配置するように指示することです。このバージョンでは、マージルーチンの外側に一時スペースを割り当てる方がよいため、割り当ては 1 回だけで済みます。前述の過剰なコピーも軽減されます。これは、 return resultステートメント (上記の疑似コードでは関数merge )の前の最後の 2 行が不要になるためです。

外部マージ ソートは、ソートするデータが大きすぎてメモリに収まらない場合に、ディスク ドライブまたはテープ ドライブを使用して実行するのが実用的です。外部ソートでは、マージソートをディスク ドライブで実装する方法について説明します。一般的なテープ ドライブ ソートでは、4 つのテープ ドライブを使用します。すべての I/O は順次実行されます (各パスの最後の巻き戻しを除く)。最小限の実装では、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. _{log 2} ( n )回でソートされたすべてのデータを含む 1 つのリストが作成されるまで繰り返します。

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

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

テープ (およびディスク) ドライブの使用を最適化する、より洗練されたマージ ソートは、多相マージ ソートです。

現代のコンピュータでは、多階層のメモリ階層が使用されるため、参照の局所性がソフトウェアの最適化において極めて重要になることがあります。マシンのメモリキャッシュへのページの出入りを最小限に抑えるように特別に選択された操作を備えた、キャッシュを考慮したマージソートアルゴリズムのバージョンが提案されています。たとえば、タイル マージ ソートアルゴリズムは、サブ配列のサイズが S に達するとサブ配列の分割を停止します。ここで S は CPU のキャッシュに収まるデータ項目の数です。これらのサブ配列はそれぞれ、挿入ソート、その後、通常のマージ ソートが標準的な再帰形式で完了します。このアルゴリズムは、キャッシュ最適化の恩恵を受けるマシンでより優れたパフォーマンスを発揮します^{[例が必要]}。(LaMarca & Ladner 1997)

マージ ソートは、分割統治法を使用しているため、並列化が良好です。このアルゴリズムの並列版が長年にわたっていくつか開発されてきました。並列マージ ソート アルゴリズムの中には、シーケンシャル トップダウン マージ アルゴリズムと密接に関連しているものもあれば、一般的な構造が異なり、K ウェイ マージ法を使用するものもあります。

シーケンシャルマージソートの手順は、分割フェーズとマージフェーズの2つのフェーズで説明できます。最初のフェーズは、サブシーケンスが簡単にソートされるまで（要素が1つまたはまったく含まれない）、同じ分割プロセスを繰り返し実行する多くの再帰呼び出しで構成されます。直感的なアプローチは、これらの再帰呼び出しを並列化することです。^{[19]次の疑似コードは、} forkキーワードとjoinキーワードを使用して、並列再帰によるマージソートを説明しています。

//配列 A の要素 lo から hi (含まない) をソートします。
アルゴリズムmergesort(A, lo, hi)は、 lo+1 < hiの場合、   // 2 つ以上の要素です。
    
        中間 := ⌊(最低 + 高) / 2⌋
        フォークマージソート(A, lo, mid)
        マージソート(A, mid, hi)
        参加する
        マージ(A、低、中、高)

このアルゴリズムは、シーケンシャル バージョンの些細な変更であり、並列化がうまくいきません。したがって、その高速化はそれほど印象的ではありません。スパンは で、シーケンシャルバージョンと比較するとのみの​​改善です(アルゴリズム入門 を参照)。これは主に、並列実行のボトルネックであるシーケンシャル マージ メソッドによるものです。 ${\displaystyle \Theta (n)}$${\displaystyle \Theta (\log n)}$

並列マージアルゴリズムを使用することで、より優れた並列性を実現できます。Cormenらは、 2つのソートされたサブシーケンスを1つのソートされた出力シーケンスにマージするバイナリバリアントを提示しています。^[19]

シーケンスの 1 つ (長さが異なる場合は長い方) で、中間のインデックスの要素が選択されます。他のシーケンス内でのその位置は、この要素がこの位置に挿入された場合にこのシーケンスがソートされたままになるように決定されます。したがって、両方のシーケンスのその他の要素のうち、それより小さい要素がいくつあるかがわかり、出力シーケンス内で選択された要素の位置を計算できます。このようにして作成された小さい要素と大きい要素の部分シーケンスに対して、再帰の基本ケースに達するまで、マージ アルゴリズムが再び並列で実行されます。

次の疑似コードは、並列マージ アルゴリズム (Cormen らから採用) を使用して修正された並列マージ ソート メソッドを示しています。

/**
 * A: 入力配列
 * B: 出力配列
 * lo: 下限
 * hi: 上限
 * オフ: オフセット
 */
アルゴリズムparallelMergesort(A, lo, hi, B, off)は
    長さ:=高 - 低 + 1
    長さ == 1の場合
        B[オフ] := A[ロー]
    それ以外の場合はT[1..len]を新しい配列とする
        中間 := ⌊(最低 + 高) / 2⌋
        ミッド':=ミッド-ロー+1
        フォーク並列マージソート(A, lo, mid, T, 1)
        並列マージソート(A, mid + 1, hi, T, mid' + 1)
        参加する 
        並列マージ(T, 1, mid', mid' + 1, len, B, off)

最悪の場合のスパンの再帰関係を分析するためには、並列実行のため、parallelMergesortの再帰呼び出しを1回だけ組み込む必要があり、

$${\displaystyle T_{\infty }^{\text{sort}}(n)=T_{\infty }^{\text{sort}}\left({\frac {n}{2}}\right)+T_{\infty }^{\text{merge}}(n)=T_{\infty }^{\text{sort}}\left({\frac {n}{2}}\right)+\Theta \left(\log(n)^{2}\right).}$$

並列マージ手順の複雑さの詳細については、「マージ アルゴリズム」を参照してください。

この再帰方程式の解は次のように与えられる。

$${\displaystyle T_{\infty}^{\text{sort}}=\Theta \left(\log(n)^{3}\right).}$$

この並列マージアルゴリズムは の並列度に達し、これは以前のアルゴリズムの並列度よりもはるかに高い。このようなソートは、挿入ソートなどの高速で安定したシーケンシャルソートと、小さな配列をマージするための基本ケースとしての高速シーケンシャルマージと組み合わせると、実際には良好なパフォーマンスを発揮する。 ^[20]${\textstyle \Theta \left({\frac {n}{(\log n)^{2}}}\right)}$

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

ソートされていない要素のシーケンスが与えられた場合、目標は利用可能なプロセッサでシーケンスをソートすることです。これらの要素はすべてのプロセッサ間で均等に分散され、順次ソート アルゴリズム を使用してローカルにソートされます。したがって、シーケンスは長さ のソートされたシーケンスで構成されます。簡略化のため、を の倍数とし、 に対して となるようにします。 ${\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})\}}$

さらに、 の要素はプロセッサ に割り当てられます。これは、ランクとランク の間のすべての要素を意味し、 全体に分散されます。したがって、各プロセッサはソートされたシーケンスのシーケンスを受け取ります。スプリッタ要素のランクがグローバルに選択されたという事実は、2 つの重要な特性を提供します。一方では、 は、各プロセッサが割り当て後も要素を操作できるように選択されています。アルゴリズムは完全に負荷分散されています。他方では、プロセッサ 上のすべての要素は、プロセッサ 上のすべての要素以下です。したがって、各プロセッサはp方向のマージをローカルに実行し、サブシーケンスからソートされたシーケンスを取得します。2 番目の特性により、さらにp方向のマージを実行する必要はなく、結果をプロセッサ番号の順序でまとめるだけで済みます。 ${\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}}$${\displaystyle k}$${\textstyle n/p}$${\displaystyle i}$${\displaystyle i+1}$

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

提示されたシーケンシャルアルゴリズムは、各シーケンス内の分割のインデックスを返します。例えば、グローバルランクが 未満で であるシーケンス内のインデックスです。^[23]${\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}$

アルゴリズム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 := ピックピボット(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モデルが選択されます。データが全体に均等に分散されている場合、 binarySearchメソッドの p 分割実行の実行時間は です。予想される再帰の深さは、通常のQuickselectと同じです。したがって、全体の予想される実行時間は です。 ${\displaystyle 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) // マージして出力配列に割り当てる
	
    戻る​

まず、各プロセッサは割り当てられた要素を複雑度のソートアルゴリズムを使用してローカルにソートします。その後、スプリッタ要素を時間 で計算する必要があります。最後に、各分割グループは、シーケンシャルp ウェイ マージ アルゴリズムを使用して、実行時間 で各プロセッサによって並列にマージする必要があります。したがって、全体の実行時間は次のように表されます。 ${\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)}$

${\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 をモデル化するときには考慮されない他の要素が重要になります。ここでは、メモリ階層、データがプロセッサのキャッシュに収まらない場合、またはプロセッサ間でデータを交換するための通信オーバーヘッドなど、次の側面を考慮する必要があります。これは、共有メモリ経由でデータにアクセスできなくなるとボトルネックになる可能性があります。

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

マージソートは最適なスピードアップが達成された最初のソートアルゴリズムの1つであり、リチャード・コールは巧妙なサブサンプリングアルゴリズムを使用してO (1)マージを保証しました。^[24]他の洗練された並列ソートアルゴリズムは、より低い定数で同じかより短い時間制限を達成できます。たとえば、1991年にデビッド・パワーズは、暗黙的にパーティション分割を実行することで、 n個のプロセッサを備えたCRCW並列ランダムアクセスマシン（PRAM）でO (log n )時間で動作できる並列クイックソート（および関連する基数ソート）を説明しました。[25] パワーズはさらに、バタフライソートネットワークでO ( ( log n ) 2 )時間のバッチャのビットニックマージソートのパイプラインバージョン^が、実際に^はPRAMでの彼のO (log n )ソートよりも高速であることを示し、比較、基数ソート、並列ソートの隠れたオーバーヘッドについて詳細に説明しています。^[26]

ヒープソートはマージソートと同じ時間制限があるが、マージソートの Θ( 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]