原理
归并排序的基础是合并有序数组，运用了分治的思想，将数组对半分，递归，直到两个数组长度都为1，可以看作两个有序数组，然后将其合并，在递归处得到长度更大的有序数组，再合并。
复杂度分析
平均时间复杂度为O(n㏒₂n)
时间复杂度最坏为O(n㏒₂n)
空间复杂度为 O(n+㏒₂n)，临时数组+递归所需栈空间
稳定。网上有空间复杂度为O(1)的实现，暂时还没研究。
代码实现
合并有序数组的实现
/**
* 合并两个有序数组
**/
private void mergeSortedArr(int a[], int b[], int c[]){
int i=0;
int j=0;
int k=0;
while (i < a.length && b < j.length){
if (a[i] < b[j]) {
c[k++] = a[i++];
} else{
c[k++] = b[j++];
}
}
while (i < a.length){
c[k++] = a[i++];
}
while (j < b.length){
c[k++] = b[j++];
}
}
归并排序实现
/**
* 归并排序
* 合并两个有序数组，分治思想
**/
public void sort(int[] a){
mergeSort(a, 0, a.length - 1, new int[a.length]);
}
private void mergeSort(int[] a, int start, int end, int[] tmp){
if (start >= end) {//递归出口
return ;
}
int middle = (start + end)/2;
mergeSort(a, start, middle, tmp);//左边有序
mergeSort(a, middle, end, tmp);//右边有序
stepSort(a, start, middle, end, tmp);//合并两个有序数组
}
private void stepSort(int[] a, int start, int middle, int end, int[] tmp){
int i = start;
int j = middle;
int k = 0;
while (i <= middle && j < end){
if (a[i] < a[j]) {
tmp[k++] = a[i++];
} else{
tmp[k++] = a[j++];
}
}
while (i <= middle){
tmp[k++] = a[i++];
}
while (j < end){
tmp[k++] = a[j++];
}
//结果写回数据源
for (i = 0; i < k; i++) {
a[i + start] = tmp[i];
}
}
