マージ ソートは、マージ操作に基づく効果的で安定した並べ替えアルゴリズムです。このアルゴリズムは、分割統治法の非常に典型的なアプリケーションです。
マージ ソートは、2 つの順序付けされたサブシーケンスを結合して、完全に順序付けされたシーケンスを取得します。つまり、最初に各サブシーケンスを並べ替えてから、サブシーケンス セグメントを並べ替えます。 2 つの順序付きリストが 1 つの順序付きリストにマージされる場合、それを双方向マージと呼びます。
マージ ソートの速度はクイック ソートに次いで 2 番目であり、時間計算量は O(nlogn) です。分割プロセスでは、再帰的なプロセスである二分法の考え方を使用します。再帰的なプロセス中にスペースが継続的に開いてしまう問題を軽減するために、マージとソートの前にまず一時的なスペースを開き、このスペースを使用します。再帰処理中に均一にマージするだけです。
例えば：
importjava.util.Arrays;publicclassMain{publicstaticvoidmain(String[]args){int[]arr=newint[]{86,23,7,45,19,10};intleft=0;intright=arr.length-1; int[]tem=Arrays.copyOf(arr,arr.length);print(arr);mergeSort(arr,left,right,tem);print(arr);}publicstaticvoidmergeSort(int[]arr,intleft,intright,int []tem){if(right-left<1){return;}intmid=left+(right-left)/2;mergeSort(arr,left,mid,tem);mergeSort(arr,mid+1,right,tem );merge(arr,left,mid,right,tem);}privatestaticvoidmerge(int[]arr,intleft,intmid,intright,int[]tem){intindex=0;intl=left,r=mid+1;while (l<=mid&&r<=right){if(arr[l]<arr[r]){tem[index++]=arr[l++];}else{tem[index++]=arr[r++];}}while( l<=mid){tem[index++]=arr[l++];}while(r<=right){tem[index++]=arr[r++];}for(inti=0;i<(right-left+1) );i++){arr[left+i]=tem[i];}}privatestaticvoidprint(int[]arr){for(inti:arr){System.out.print(i+t);}System.out。 println();}} 実行結果は次のとおりです。
8623745191071019234586