在前几篇文章中我们学习了选择排序，插入排序，以及插入排序的优化版希尔排序，但是他们的时间复杂度都是O(N^2)，现在我们终于迎来了我们算法效率大幅度提升的，时间复杂度为O(NlogN)算法——归并排序。
归并排序的具体含义就是合并两个有序的数组，使数组合并成为一个数组，并且合成的这一个数组整个内部都是有序的。当我们有了这个归并的算法之后，我们就可以用递归来把整个数组一分为二，二分为四，以此类推。最终我们会得到很小的数组。把这些小数组合并为有序的，最终我们就会得到整个有序的大数组。这也是分治方法的具体应用。
下面先讲一下归并的算法，首先开门见山，直接上代码。
public static void merge(int[] num,int[] temp,int lo, int mid, int hi){
//其实并不是真正意义上的把数组分成两个，而是假想的，lo代表前面数组的第一个元素，mid代表前面数组的最后一个元素，hi表示后面数组的最后一个元素。
int i = lo;
int j = mid+1;
for (int k = lo; k <= hi; k++) {
temp[k] = num[k];//temp是辅助数组。
}
for(int k = lo;k <= hi;k++){
if(i > mid) num[k] = temp[j++];//如果前半部分数组空了以后，直接把后面的数组放入辅助数组。
else if(j > hi) num[k] = temp[i++];//后半部分数组满了以后，直接把前面的数组放入辅助数组。
else if(temp[i] < temp[j]) num[k] = temp[i++];//谁小谁放入辅助数组，然后相对应的指针加一。
else num[k] = temp[j++];
}
}
好了，到了现在我们已经有了最基本归并算法，下面我们就可以通过这个算法然后递归得到完整的归并排序算法。废话不多说，先上代码。
public class mergesort {
public static void main(String[] args) {
int[] num = {3,44,38,5,47,15,36,26,27,2,46,4,1,50,48，32};//待处理的数组。
mergeloop(num);
System.out.println(Arrays.toString(num));
}
public static void sort(int[] num,int[] temp,int lo,int hi){
if(lo>=hi)return;
int mid = (lo+hi)/2;
sort(num,temp,lo,mid);//mid代表前面数组中的最后一个元素，先把前半部分排好序。
sort(num,temp,mid+1,hi);//在把后面部分排好序。
merge(num,temp,lo,mid,hi);//然后将前面的部分和后面的部分归并排序，行成一个完整的有序的大数组。
}
public static void sort(int[] num){
//这个函数创建的意义就是一次性把辅助数组给创建出来，而不是放入上面的递归的函数中，那样大部分时间就会花在来回创建数组上，会导致算法的效率大幅度降低。
int[] temp = new int[num.length];
sort(num,temp,0,num.length-1);
}
public static void merge(int[] num,int[] temp,int lo, int mid, int hi){
int i = lo;
int j = mid+1;
for (int k = lo; k <=hi; k++) {
temp[k] = num[k];
}
for(int k = lo;k <= hi;k++){
if(i > mid) num[k] = temp[j++];
else if(j>hi) num[k] = temp[i++];
else if(temp[i] < temp[j]) num[k] = temp[i++];
else num[k] = temp[j++];
}
}
}
其实这个递归算法并不难想，也很好理解，但考虑到我博客的全面性，我还是简要的用递归的概念解释一下代码。
**递归调用的函数会不断的压栈，然后等到lo>=hi,然后函数进行出栈。**然后我写出函数的调用轨迹你们就理解上面的整个调用过程了。
sort(num,0,15)//前半部分
sort(num,0,7)
sort(num,0,3)
sort(num,0,1)
merge(num,0,0,1)
sort(num,2,3)
merge(num,2,2,3)
merge(num,0,1,3)
sort(num,4,7)
sort(num,4,5)
merge(num,4,4,5)
sort(num,6,7)
merge(num,6,6,7)
merge(num,4,5,7)
merge(num,0,3,7)
sort(num,8,15)//后半部分
sort(num,8,11)
sort(num,8,9)
merge(num,8,8,9)
sort(num,10,11)
merge(num,10,10,11)
merge(num,8,9,11)
sort(num,12,15)
sort(num,12,13)
merge(num,12,12,13)
sort(num,14,15)
merge(num,14,14,15)
merge(num,12,13,15)
merge(num,8,11,15)
merge(num,0,7,15)归并结果。
以上就是归并排序的整个调用过程了，相信现在大家都已经懂了吧。
众所周知，一般来说能用递归实现的问题都能用for循环来实现，下面我们就写出用for循环来演示归并排序的算法。废话不多说，先上代码。
public static void mergeloop(int[ ] num){
int N = num.length;
int[] temp = new int[num.length];
for(int sz = 1;sz <= N;sz = sz+sz){//sz表示数组的大小。我们把一个元素假定为一个数组。sz为1，2，4，8，16.
for(int lo = 0;lo < N-sz;lo+=sz+sz){lo表示假想的前面那个数组的头部索引。
merge(num,temp,lo,lo+sz-1,Math.min(lo+sz+sz-1,N-1));
//lo+sz-1表示前面那个数组的末尾，就相当于上面的mid。
//后面之所以用Math.min(lo+sz+sz-1,N-1)，是因为到最后的时候数组不一定对称。找到最小的。
}
}
}
sz=1：
merge(num,0,0,1)
merge(num,2,2,3)
merge(num,4,4,5)
merge(num,6,6,7)
merge(num,8,8,9)
merge(num,10,10,11)
merge(num,12,12,13)
merge(num,14,14,15)
sz=2:
merge(num,0,1,3)
merge(num,4,5,7)
merge(num,8,9,11)
merge(num,12,13,15)
sz=4:
merge(num,0,3,7)
merge(num,8,11,15)
sz=8:
merge(num,0,7,15)
好了，到现在我们已经把归并排序的递归版和归并排序的循环版都讲完了，并且已经把整个函数的调用过程都写了出来，这样一来就没有什么不懂得了吧。归并排序的排序效率已经比较之前的算法效率已经大幅度提升了。下面我们就会讲快速排序了。
本人良弓，初来乍到，请多关照。~