歸併排序（Merge Sort）是建立在歸併操作上的一種有效的穩定的排序演算法，該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。
歸併排序將兩個有序的子序列合併得到一個完全有序的序列，即先使每個子序列有序，再使子序列段間有序。若將兩個有序的列表合併成一個有序的列表，我們稱之為二路歸併。
歸併排序的速度僅次於快速排序，時間複雜度為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