归并排序和快速排序类似也是采用分治法的一种排序，时间复杂度O(nlog2n)，但它是牺牲空间换时间的方式，过程中多次创建新数组，所以很消耗内存。
描述：
1、首先将待排序数组递归二分成N个单元素数组，此时所有的子数组都是有序的（因为只有一个元素）;
2、把两个有序的数组合并成一个有序的数组，递归直到所有的子数组合并成原先的数组，排序完成。
动画：
归并排序动画.gif
代码：
private void mergeSort(int[] array, int start, int end) {
if (array.length <= 1 || start >= end) {
return;
}
//取分割点
int mid = (start + end) / 2;
//分割成左右两个数组
mergeSort(array, start, mid);
mergeSort(array, mid + 1, end);
//分割后取左右两个有序数组合并成新的有序数组
merge(array, start, mid + 1, end);
}
private void merge(int[] array, int start, int mid, int end) {
int[] leftArray = new int[mid - start];
int[] rightArray = new int[end - mid + 1];
//从mid位置将array分成两个数组
for (int i = start; i <= end; i++) {
if (i < mid) {
leftArray[i - start] = array[i];
} else {
rightArray[i - mid] = array[i];
}
}
int i = 0;
int j = 0;
int k = start;
while (i < leftArray.length && j < rightArray.length) {
//两个新数组中优先将小的元素取出重新放回array中
//array逐渐变得有序
if (leftArray[i] < rightArray[j]) {
array[k++] = leftArray[i++];
} else {
array[k++] = rightArray[j++];
}
}
//若两个新数组中有一个数组数据取完
//则将另一个数组剩下的数据依次取出放回array中
while (i < leftArray.length) {
array[k++] = leftArray[i++];
}
while (j < rightArray.length) {
array[k++] = rightArray[j++];
}
}
