Merge Sort adalah algoritma pengurutan yang efektif dan stabil berdasarkan operasi penggabungan. Algoritma ini adalah aplikasi yang sangat umum dari metode bagi dan taklukkan .
Pengurutan gabungan menggabungkan dua urutan berikutnya untuk mendapatkan urutan yang terurut lengkap, yaitu, pertama-tama buatlah setiap urutan berikutnya, lalu buatlah segmen-segmen berikutnya diurutkan. Jika dua daftar terurut digabungkan menjadi satu daftar terurut, kami menyebutnya penggabungan dua arah .
Kecepatan pengurutan gabungan adalah yang kedua setelah pengurutan cepat, dan kompleksitas waktunya adalah O(nlogn). Proses pemisahan menggunakan ide dikotomi, yaitu proses rekursif, untuk mengurangi masalah pembukaan ruang yang terus menerus selama proses rekursif, terlebih dahulu kita dapat membuka ruang sementara sebelum menggabungkan dan menyortir, dan menggunakan ruang tersebut. secara seragam selama proses rekursif.
Misalnya:
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,kiri,kanan,tem);print(arr);}publicstaticvoidmergeSort(int[]arr,intleft,intright,int []tem){if(kanan-kiri<1){return;}intmid=kiri+(kanan-kiri)/2;mergeSort(arr,kiri,tengah,tem);mergeSort(arr,mid+1,kanan,tem) );merge(arr,kiri,tengah,kanan,tem);}privatestaticvoidmerge(int[]arr,intleft,intmid,intright,int[]tem){intindex=0;intl=kiri,r=mid+1;sementara (l<=pertengahan&&r<=kanan){if(arr[l]<arr[r]){tem[index++]=arr[l++];}else{tem[index++]=arr[r++];}}sementara( l<=pertengahan){tem[index++]=arr[l++];}sementara(r<=kanan){tem[index++]=arr[r++];}for(inti=0;i<(kanan-kiri+1 );i++){arr[left+i]=tem[i];}}privatestaticvoidprint(int[]arr){for(inti:arr){System.out.print(i+t);}System.out. println();}} Hasil yang berjalan adalah sebagai berikut:
8623745191071019234586