思想
归并排序的中心思想是分值。把两个已经排序的文件合并成一个更大的已排序的文件。
算法包括两个部分，一个部分是拆分，将数组拆分成包含k个元素和n-k个元素的两个数组的过程。这个过程每一次都将数组折半拆分。
另一部分是合并，将已排序的小数组合并成排序的大数组。
下面看图就明白这个过程：
例子
如上图所示。
分析
时间复杂度：O(nlogn);
总时间=分解时间+解决问题时间+合并时间。 分解时间就是把一个待排序序列分解成两序列，时间为一常数，时间复杂度o(1).
解决问题时间是两个递归式，把一个规模为n的问题分成两个规模分别为n/2的子问题，时间为2T(n/2).合并时间复杂度为o（n）。
总时间T(n)=2T(n/2)+o(n).这个递归式可以用递归树来解，其解是o(nlogn).
此外在最坏、最佳、平均情况下归并排序时间复杂度均为o(nlogn).从合并过程中可以看出合并排序稳定。 用递归树的方法解递归式T(n)=2T(n/2)+o(n):假设解决最后的子问题用时为常数c，则对于n个待排序记录来说整个问题的规模为cn。
空间复杂度：O(n)需要一个临时数组存储
稳定性：相等的元素的顺序不会改变，所以它是稳定的算法。
代码
package test;
import java.util.Arrays;
public class mergeSort {
public static void main(String[] args) {
mergeSort sort = new mergeSort();
int [] nums = {8,3,2,6,7,1,4,5};
sort.mergesort(nums, 0, nums.length - 1);
System.out.println(Arrays.toString(nums));
}
public void mergesort(int [] nums,int left,int right){
int mid = (left + right)/2;
if (left < right) {
// 左边排序
mergesort(nums, left, mid);
// 右边排序
mergesort(nums, mid + 1, right);
// 左右合并
merge(nums, left, mid, right);
}
}
public void merge(int [] numbers,int left,int mid,int right){
int tempIndex = 0;
int []temp = new int[right - left + 1];
int i = left;// 指向第一个数组的指针
int j = mid + 1; // 指向第二个数组的指针
while (i <= mid && j <= right) {
if (numbers[i] < numbers[j]) {
temp[tempIndex] = numbers[i];
i++;
tempIndex ++;
}else{
temp[tempIndex] = numbers[j];
j++;
tempIndex ++;
}
}
// 前面的数组还没遍历完，就将其添加到temp的后面
while (i <= mid) {
temp[tempIndex ++] = numbers[i++];
}
// 后面的数组没有便利完，就将其顺序添加到temp末尾
while (j <= right) {
temp[tempIndex++] = numbers[j++];
}
// 排好序的临时数组覆盖原数组的某一段
for(int n = 0;n < temp.length;n++){
numbers[left + n] = temp[n];
}
}
}
