归并排序
1、原理
归并排序是一种概念上最简单的排序算法，与快速排序一样，归并排序也是基于分治法的。归并排序将待排序的元素序列分成两个长度相等的子序列，为每一个子序列排序，然后再将他们合并成一个子序列。合并两个子序列的过程也就是两路归并。
2、复杂度
归并排序是一种稳定的排序算法，归并排序的主要问题在于它需要一个与待排序数组一样大的辅助数组空间。由于归并排序每次划分时两个子序列的长度基本一样，所以归并排序最好、最差和平均时间复杂度都是nlog2n。
我们可以通过下图非常容易看懂归并排序的过程：
要将两个排好序的子序列合并为一个子序列的方法：每次都是从未比较的两个子序列的最小值中选出一个更小值。
复杂度：
3、完整Java代码
import org.junit.Test;public class MergeSort {//两路归并算法，两个排好序的子序列合并为一个子序列public void merge(int []a,int left,int mid,int right){int []tmp=new int[a.length];//辅助数组int p1=left,p2=mid+1,k=left;//p1、p2是检测指针，k是存放指针while(p1<=mid && p2<=right){if(a[p1]<=a[p2])tmp[k++]=a[p1++];elsetmp[k++]=a[p2++];}while(p1<=mid) tmp[k++]=a[p1++];//如果第一个序列未检测完，直接将后面所有元素加到合并的序列中while(p2<=right) tmp[k++]=a[p2++];//同上//复制回原素组for (int i = left; i <=right; i++) a[i]=tmp[i];}public void mergeSort(int [] a,int start,int end){if(start<end){//当子序列中只有一个元素时结束递归int mid=(start+end)/2;//划分子序列mergeSort(a, start, mid);//对左侧子序列进行递归排序mergeSort(a, mid+1, end);//对右侧子序列进行递归排序merge(a, start, mid, end);//合并}}@Testpublic void test(){int[] a = { 49, 38, 65, 97, 76, 13, 27, 50 };mergeSort(a, 0, a.length-1);System.out.println("排好序的数组：");for (int e : a)System.out.print(e+" ");}}
4、归并与快排的比较
在同一台计算机上得到两个算法在不同数组长度下的执行时间：
快排和归并的理论上的时间复杂性如下表：
（1）在数组长度小于一千万的时候，如下图，快速排序的速度要略微快于归并排序，可能是因为归并需要额外的数组开销（比如声明临时local数组用来储存排序结果），这些操作让归并算法在小规模数据的并不占优势。
（2）但是，当数据量达到亿级时，归并的速度开始超过快速排序了，如下图，因为归并排序比快排要稳定，所以在数据量大的时候，快排容易达到O(n^2)的时间复杂度，当然这里是指未改进的快排算法。
