1.思想
归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略
分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之。
总结来说(重点)：把序列不断对半拆分，直到分到仅剩一个元素，将它们排序合并；然后处理两个元素的序列，排序合并，如此类推。
分而治之：
分：从上往下，直到拆分到一个元素
治：从下往上，从单个元素合并成一条有序的序列
再来看最后的合并阶段，算法实现只需要维护两个左右指针即可。
Java代码实现
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
int [] arr = {1,5,6,4,9,2,3,8,7};
Sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void Sort(int arr[]){
int [] temp = new int[arr.length];//开辟一个原数组长度一样的数组，避免递归的时候频繁开辟空间
Divide(arr,0,arr.length-1,temp);
}
public static void Divide(int [] arr,int left,int right,int [] temp){
if(left
int mid = (left+right)/2; //每次规模减少一半
Divide(arr,left,mid,temp); //右边序列的排序并且归并为一个数组
Divide(arr,mid+1,right,temp);//左边序列的排序并且归并为一个数组
Merge(arr,left,mid,right,temp);//合并两个数组
}
}
public static void Merge(int [] arr,int left,int mid,int right,int [] temp){
int i = left;
int j = mid+1;
int t = 0;
// 左右两边移动指针比较，取较小的一个数放进temp数组
while (i<=mid && j<=right){
if (arr[i]<=arr[j]){
temp[t++] = arr[i++];
}else {
temp[t++] = arr[j++];
}
}
// 把左或右多出的数，推入数组
while (i<=mid){
temp[t++] = arr[i++];
}
while(j<=right){
temp[t++] = arr[j++];
}
// 最后把temp数组替换原数组
t = 0;
while (left<=right){
arr[left++] = temp[t++];
}
}
}
2.算法分析
归并排序的时间复杂度包括分解，比较，合并。
最好的情况下，数组是已排序的，那么归并排序的时间复杂度为O(n)级的。
最坏的情况下，数组是逆序的，那么归并排序的时间复杂度为O(nlogn)级的。归并排序的平均时间复杂度是O(nlogn)。
