“归并”的含义是将两个或者两个以上的有序表组合成一个新的有序表。
假设待排序表含有n个元素，则可以看成是n个有序的子表，每个子表的长度为1，然后两两归并，得到（n/2）或者（n/2+1）个长度为2或1的有序表；再两两归并。。。
如此重复，直到合并成一个长度为n的有序表为止。
这种方法称为二路归并排序算法。
直接上代码：
package com.mergeSort;
public class MergeSort {
//归并排序的对外公共接口
public static void mergeSort(int arr[],int n){
subMergeSort(arr,0,n-1);
}
//实现归并排序
private static void subMergeSort(int[] arr, int l, int r) {
//当l=r时即将待排序序列二分到每组只有一个元素时，对于一个元素来说，它自己就是有序的
if(l>=r)
return;
int mid=(l+r)/2;
subMergeSort(arr,l,mid);//归并排序前半段
subMergeSort(arr,mid+1,r);//归并排序后半段
//将两段有序序列归并成一段有序序列
mergeSortCore(arr,l,mid,r);
}
//将两段有序序列归并成一段有序序列
//对arr[l...mid]和arr[mid+1,r]两部分进行归并
private static void mergeSortCore(int[] arr, int l, int mid, int r) {
//开辟出辅助数组
int[] a=new int[r-l+1];
//将原数组全部元素复制到辅助数组
for(int i=l;i<=r;i++)
a[i-l]=arr[i]; //a数组是从0开始的，因此和arr数组存在l个偏移量
//定义两个指针，分别指向两段有序序列的起始位置
int j=mid+1;
int i=l;
//用k作指针将排序后的数组元素重新放到原数组arr[l...r]中
for(int k=l;k<=r;k++){
//当前半段都放入arr中而后半段还没有遍历完
if(i>mid){
arr[k]=a[j-l];
j++;
}else
//当后半段都放入arr中而前半段还没有遍历完
if(j>r){
arr[k]=a[i-l];
i++;
}
else
//若两段都没遍历完，那么就比较一下
if(a[i-l]<a[j-l]){
arr[k]=a[i-l];
i++; //别忘了每搞定一个元素，指针的后移
}
else
{
arr[k]=a[j-l];
j++;
}
}
}
public static void main(String[] args){
int[] arr=new int[]{10,9,8,7,6,5,4,3,2,1};
mergeSort(arr,10);
for(int i=0;i<arr.length;i++)
System.out.print(arr[i]+" ");
}
}
注意：
1）归并排序需要一个新建一个辅助数组；
2）本段代码中排序数组的每段都是两头包括的闭区间，例如arr[l...mid]。当然也可以定义成一头开一头闭的区间，例如arr[l...mid+1），只不过相关代码需要做相应的改动。
3）代码中划下划线的部分，即 int mid=(l+r)/2; 在数据量很大的时候（即l和r很大的时候），有可能会造成mid的值的溢出。
4）该排序算法的时间复杂度为O（nlog2n）。
5）是稳定的。
对二路排序算法的优化：
1）在上面代码中实现归并排序的subMergeSort方法中有这么一个片段：
subMergeSort(arr,l,mid);//归并排序前半段
subMergeSort(arr,mid+1,r);//归并排序后半段
//将两段有序序列归并成一段有序序列
mergeSortCore(arr,l,mid,r);
这段代码中，我们对每一次单独排序完的两段都进行了一次mergeSortCore()方法的归并操作。
但是因为这两段各自内部都是有序的，那么当arr[mid]<=arr[mid+1]时，我们就没有必要再去操作mergeSortCore()方法，
因此我们可以加个判断语句，来省掉多余的操作。
subMergeSort(arr,l,mid);//归并排序前半段
subMergeSort(arr,mid+1,r);//归并排序后半段 //当arr[mid]<=arr[mid+1]时证明整个arr数组就已经有序了，那么此时根本不需要调用mergeSortCore方法
//只有当arr[mid]>arr[mid+1]时，我们才有必要执行mergeSortCore方法
if(arr[mid]>arr[mid+1]) //将两段有序序列归并成一段有序序列
mergeSortCore(arr,l,mid,r);
2）几乎对于所有的高级排序算法，有一种通用的优化，那就是在递归到底的情况下，可以使用直接插入排序进行优化。
当递归几乎到底时，每一组只有有限数量的元素，而元素越少，那么倾向于有序的几率越大。虽然直接插入排序的时间复杂度是O(n2),但是我们知道在元素趋向于有序时，它甚至可以高效运行使得时间复杂度达到O（n）。
同时，对于时间复杂度前面的系数大小，直接插入排序是比归并排序小的。
因此，当n小到一定程度，直接插入排序会比归并排序要快。
所以对于上面代码中实现归并排序的subMergeSort方法中的一个片段：
if(l>=r)
return;
改为：
if(r-l<=15){
insertionSort(arr,l,r);
return;
}
其中，insertionSort()方法是已经定义的实现闭区间直接插入排序的方法。
数字15也可以设置为其他数值。
从以上代码的执行过程来看，这是一种自上而下的归并排序算法。
对于自下而上的归并排序算法：
public static void mergeSortBtoU(int[] arr,int n){
//自下而上的归并排序算法
//第一层循环对参与mergeSortCore的元素个数进行遍历，第一次为1个，第二次为2个，第三次为4个，第四次为8个。。。。
//从每一个单个元素开始作为归并小组进行归并，每一次归并成的结果是归并前原小组规模的二倍（即sz+=sz）
//当归并小组规模达到整个待排序数组大小的时候（即sz<=n），完成归并排序算法
for(int sz=1;sz<=n;sz+=sz)
//i为每一次进行mergeSortCore排序的元素的起始位置（每次进行两组元素的归并排序）
//每一次归并两组，每组的大小为sz，所以每次i的移动幅度为两个sz（即i+=sz+sz）
//用第二部分起始位置（i+sz）小于n，来限制每次归并时第二部分的存在，同时也保证了（i+sz-1）不会出现越界问题
for(int i=0;i+sz<n;i+=sz+sz)
//对arr[i...i+sz-1]和arr[i+sz...i+2*sz-1]进行归并
//对于将要进行归并的第二部分可能出现不足sz大小的情况，即（i+sz+sz-1可能出现越界问题）
//故用Math的min()方法进行限制
MergeSort.mergeSortCore(arr, i, i+sz-1, Math.min(i+sz+sz-1,n-1));
}
对此，也可进行优化操作。
另，对于自下而上的归并排序算法，没有使用数组中一个重要的性质：使用索引直接确定元素位置。因此，这种算法可以以时间复杂度为O(nlog2n)的速度对链表进行排序。