Java ソートアルゴリズムの概要 (V): マージソート

マージソートとは、2つ（またはそれ以上）の順序付きリストを新しい順序付きリストにマージすることです。つまり、ソートするシーケンスを複数のサブシーケンスに分割し、各サブシーケンスを順序付けます。次に、順序付けられたサブシーケンスを全体の順序付けられたシーケンスにマージします。

マージソートは、マージ操作に基づいた効果的なソートアルゴリズムです。このアルゴリズムは、分割統治法の非常に典型的な応用です。順序付けられたサブシーケンスをマージして、完全に順序付けられたシーケンスを取得します。つまり、最初に各サブシーケンスを順序付けし、次にサブシーケンスのセグメントを順序付けます。 2 つの順序付きリストが 1 つの順序付きリストに結合される場合は、2 方向の結合と呼ばれます。

マージソートアルゴリズムは安定しています。配列の場合は O(n) の追加スペースが必要で、リンクリストの場合は O(log(n)) の追加スペースが必要です。時間の計算量は O(nlog(n)) です。このアルゴリズムは適応型ではなく、データのランダム読み取りを必要としません。

動作原理:

1. 2 つのソートされたシーケンスの合計と同じサイズになるようにスペースを申請します。このスペースは、結合されたシーケンスを格納するために使用されます。

2. 2 つのポインタを設定します。その初期位置は、ソートされた 2 つのシーケンスの開始位置になります。

3. 2つのポインタが指す要素を比較し、比較的小さい要素を選択してマージスペースに配置し、ポインタを次の位置に移動します。

4. ポインタがシーケンスの最後に到達するまで手順3を繰り返します。

5. 他のシーケンスの残りの要素をすべて、結合されたシーケンスの末尾に直接コピーします。

コード実装:

公共  voidマージソート(){
 long [] ワークスペース = new  長い[n要素];
 recMergeSort(ワークスペース、 0 、n要素 - 1 );
 }
プライベート  void recMergeSort( long [] workSpace, int lowerBound, int upperBound){
 (下限値 == 上限値)の場合{
戻る;
 }
それ以外{
 int mid=(lowerBound+upperBound)/ 2 ;
 recMergeSort(ワークスペース、lowerBound、mid);
 recMergeSort(ワークスペース、mid+ 1 、upperBound);
マージ(ワークスペース、下限、中間+ 1 、上限);
 }
 }
プライベート  void merge( long [] workSpace、 int lowPtr、 int highPtr、 int upperBound){
整数j = 0 ;
 int下限値 = lowPtr;
 int mid = highPtr - 1 ;
 int n = 上限 - 下限 + 1 ;
 (lowPtr<=mid&&highPtr<=upperBound)の場合{
 （配列[lowPtr]<配列[highPtr]）の場合{
ワークスペース[j++] = theArray[lowPtr++];
 }
それ以外{
ワークスペース[j++] = theArray[highPtr++];
 }
 }
 (lowPtr<=mid)の間{
ワークスペース[j++] = theArray[lowPtr++];
 }
 (highPtr<=upperBound)の場合{
ワークスペース[j++] = theArray[highPtr++];
 }
 (j= 0 ;j<n;j++)の場合{
配列[下限+j] = ワークスペース[j];
 }
 }

マージソートは比較的安定したソートです。つまり、同じ要素の順序は変わりません。例えば、入力レコードが 1(1) 3(2) 2(3) 2(4) 5(5) の場合（括弧内のキーワードはレコードのキーです）、出力 1(1) 2(3) 2(4) 3(2) 5(5) は入力順で 2 と 2 になります。これは、ソートするデータに複数の情報が含まれており、そのうちの 1 つの情報でソートし、他の情報はできるだけ入力順に並べたい場合に非常に重要です。これもクイックソートに対する利点です。

【編集者のおすすめ】