Merge Sort เป็นอัลกอริธึมการเรียงลำดับที่มีประสิทธิภาพและเสถียรโดยอิงจากการดำเนินการผสาน อัลกอริธึมนี้เป็นการประยุกต์ใช้ วิธีแบ่งและพิชิต โดยทั่วไป
การเรียงลำดับแบบผสานจะรวมลำดับย่อยสองลำดับเข้าด้วยกันเพื่อให้ได้ลำดับที่สมบูรณ์ กล่าวคือ ขั้นแรกให้เรียงลำดับแต่ละลำดับย่อย จากนั้นจึงเรียงลำดับเซ็กเมนต์ลำดับย่อย หากมีการรวมรายการที่เรียงลำดับสองรายการเข้าด้วยกันเป็นรายการเรียงลำดับเดียว เราจะเรียกมันว่า การผสานแบบสองทาง
ความเร็วของการเรียงลำดับแบบผสานเป็นรองเพียงการเรียงลำดับอย่างรวดเร็ว และความซับซ้อนของเวลาคือ O(nlogn) กระบวนการแยกใช้แนวคิดของ dichotomy ซึ่งเป็นกระบวนการแบบเรียกซ้ำ เพื่อลดปัญหาการเปิดพื้นที่อย่างต่อเนื่องในระหว่างกระบวนการแบบเรียกซ้ำ ก่อนอื่นเราสามารถเปิดพื้นที่ชั่วคราวก่อนที่จะรวมและเรียงลำดับและใช้พื้นที่นี้ สม่ำเสมอในระหว่างกระบวนการเรียกซ้ำ เพียงแค่ผสาน
ตัวอย่างเช่น:
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);พิมพ์(arr);mergeSort(arr,ซ้าย,ขวา,tem);พิมพ์(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) );ผสาน(arr,ซ้าย,กลาง,ขวา,tem);}privatestaticvoidmerge(int[]arr,intleft,intmid,intright,int[]tem){intindex=0;intl=left,r=mid+1;ในขณะที่ (l<=กลาง&&r<=right){if(arr[l]<arr[r]){tem[index++]=arr[l++];}else{tem[index++]=arr[r++];}}ในขณะที่( l<=mid){tem[index++]=arr[l++];} while(r<=right){tem[index++]=arr[r++];}for(inti=0;i<(ขวา-ซ้าย+1 );i++){arr[left+i]=tem[i];}}privatestaticvoidprint(int[]arr){for(inti:arr){System.out.print(i+t);}System.out. พิมพ์ ();}} ผลการวิ่งมีดังนี้:
8623745191071019234586