归并排序（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