归并排序是一个时间复杂度为O(nlogn)的排序算法
归并排序的核心思想如下：
如果要排序一个数组，先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。
归并排序使用的就是分治思想。
分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。
小的子问题解决了，大问题也就解决了。
首先使用递归实现归并排序：
privatestaticvoidmergeInternal(int[]array,intlow,inthigh)
{
if(low=high){
return;
}
intmid=(low+(high-low)/2);
//左边小数组
mergeInternal(array,low,mid);
//右边小数组
mergeInternal(array,mid+1,high);
//合并
merge(array,low,mid,high);
}
合并函数的实现：
如图所示，申请一个临时数组tmp，大小与array[p…r]相同。
用两个游标i和j，分别指向array[p…mid]和array[mid+1…r]的第一个元素。
比较这两个元素array和array[j]，如果array=array[j]，就把array放入到临时数组tmp，并且i后移一位，否则将array[j]放入到数组tmp，j后移一位。
继续上述比较过程，直到其中一个子数组中的所有数据都放入临时数组中，再把另一个数组中的数据依次加入到临时数组的末尾，这个时候，临时数组中存储的就是两个子数组合并之后的结果了。
最后再把临时数组tmp中的数据拷贝到原数组array[p…r]中。
eg:归并排序代码实现
publicstaticvoidmerge(int[]array,intp,intq,intr){
inti=p;
intj=q+1;
int[]temp=newint[r-p+1];
intk=0;
//此时俩个数组均有元素
while(i=qj=r){
if(array=array[j]){
temp[k++]=array[i++];
}else{
temp[k++]=array[j++];
}
}
//判断当前还有哪个数组没有走完
intstart=i;
intend=q;
//假如第二个小数组没有走完
if(j=r){
start=j;
end=r;
}
//把剩余元素直接放置在temp数组即可
while(start=end){
temp[k++]=array[start++];
}
//将临时空间中已经合并好的数组拷贝回原数组
for(i=0;ir-p+1;i++){
array[p+i]=temp;
}
publicstaticvoidmergeSort(int[]array){
longstart=System.currentTimeMillis();
intn=array.length;
if(n=1){
return;
}
intmid=n/2;
mergeInternal(array,0,n-1);
longend=System.currentTimeMillis();
System.out.println("归并排序耗时："+(end-start)+"毫秒");
}
算法总结：
在合并的过程中，如果A[p…q]和A[q+1…r]之间有值相同的元素，那我们可以像伪代码中那样，先把A[p…q]中的元素放入tmp数组。这样就保证了值相同的元素，在合并前后的先后顺序不变。所以，归并排序是一个稳定的排序算法
归并排序的时间复杂度是O(nlogn)。
从我们的原理分析和伪代码可以看出，归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是O(nlogn)。
每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过n个数据的大小，所以空间复杂度是O(n)。