归并排序的描述
归并排序是将两个有序的数列合并成一个有序的数列。给定一个一维无序数组，递归拆分成两个子数组，直到每个子数组中只有一个元素，将两个子数组的两个元素合并为一个有序数列，再向上依次合并，最后整个数组有序。
归并排序的分析
归并排序是典型的以空间换时间的算法。额外的数组空间用来暂存排序的结果，时间复杂度是O(nlogn)，空间复杂度是O(n)。
如下图展示归并排序的过程：
归并排序的过程
在初始的无序数列中，PartA和PartB都是有序的部分，两者合并成一个更大的有序数列1，同样的无序数列其他部分（例如，PartC，PartD等）依次合并；多个有序的数列（有序1，有序2等），这些有序数列再次两两合并，最终直到成为一个完整的有序数列。
归并排序升序排序的代码
public void mergeSort(int[] array, int[] tmpArray, int left, int right){
//递归实现归并排序
if (left < right){
int mid = (left + right)/2;
mergeSort(array, tmpArray, left, mid);
mergeSort(array, tmpArray, mid + 1, right);
//将部分有序数列合并为一个更大的有序数列
merge(array, tmpArray, left, mid, right);
}
}
private void merge(int[] array, int[] tmpArray, int left, int mid, int right){
int lStart = left; int lEnd = mid; int rStart = mid + 1; int rEnd = right;
int k = left;
//合并两个有序子数组为一个完整的有序数组，结果存储在暂存数组中
while(lStart <= lEnd && rStart <= rEnd){
if (array[lStart] < array[rStart]){
tmpArray[k] = array[lStart];
lStart++;
} else {
tmpArray[k] = array[rStart];
rStart++;
}
k++;
}
while (rStart <= rEnd){
tmpArray[k++] = array[rStart++];
}
while (lStart <= lEnd){
tmpArray[k++] = array[lStart++];
}
//从暂存数组拷贝有序数列到原来数组中
for (int i = left; i <= right; ++i){
array[i] = tmpArray[i];
}
}
