归并排序 (Merge Sort)
归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。
基本思想
归并排序是用分治思想，分治模式在每一层递归上有三个步骤：
1，分解（Divide）：将n个元素分成个含n/2个元素的子序列。
2，解决（Conquer）：用合并排序法对两个子序列递归的排序。
3，合并（Combine）：合并两个已排序的子序列已得到排序结果。
示例(递归思想)
1，自顶向下排序
//合并俩个有序的区间 arr[l, mid] 和 arr[mid + 1, r]
private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r){
//[0..arr.length]
E[]temp = Arrays.copyOfRange(arr, l, r+1);
//i是[l, mid] 第一个元素，j是[mid + 1, r] 第一个元素
int i = l, j = mid + 1;
//循环为arr[k]赋值
for (int k = l; k <= r; k++) {
if (i > mid) {
arr[k] = temp[j - l];
j ++;
} else if (j > r) {
arr[k] = temp[i - l];
i ++;
}else if (temp[i - l].compareTo(temp[j - l]) <= 0){
arr[k] = temp[i - l];
i ++;
} else {
arr[k] = temp[j - l];
j ++;
}
}
}
//升序排列数组
public static <E extends Comparable<E>> void sort(E[] arr) {
sort(arr, 0, arr.length - 1);
}
private static <E extends Comparable<E>> void sort(E[] arr, int l, int r){
if (l >= r) return;
int mid = l + (r - l) /2 ;
sort(arr, l , mid);
sort(arr, mid + 1, r);
//有序数组可不进行merge 时间复杂度改变的重要原因。
if (arr[mid].compareTo(arr[mid + 1]) > 0) // 优化1：O(nlogn) -> O(n)
merge(arr, l , mid, r);
}
自顶向下
2，自底向上排序
//自底向上
public static <E extends Comparable<E>> void sortBU(E[] arr){
E[] temp = Arrays.copyOf(arr, arr.length);
int n = arr.length;
//sz 合并的区间长度 1 2 4 8
for (int sz = 1; sz < n; sz += sz) {
//遍历合并的俩个区间的起始位置
// 合并[i, i + sz - 1] 和[ i + sz, i + sz + sz - 1]
//如果第二个区间存在 前一个区间也存在 i + sz < n
//Math.min( i + sz + sz - 1, n - 1) 取小最后可能越界 [1, 3, 5, 7, |9, 10]
for (int i = 0; i + sz < n; i += sz + sz) {
if (arr[i + sz - 1].compareTo(arr[i + sz]) > 0 )
merge2(arr, i, i + sz - 1, Math.min( i + sz + sz - 1, n - 1), temp);
}
}
}
合并2个长度为1的数组
合并2个长度为2的数组
合并2个长度为4的数组
数据不成比例
时间复杂度：
平均时间复杂度：O(nlogn)
最佳时间复杂度(完全有序数组)：O(n)
最差时间复杂度：O(nlogn)
空间复杂度：O(n)
递归深度：O(logn)
随机数组复杂度分析
完全有序数组：O(n)
有序数组复杂度分析
有序数组复杂度分析
优化：
归并排序算法不是原地排序算法
- 判断是否需要merge
- 对小规模数据使用插入排序
- 只创建一个临时空间
相关题目
稳定性
排序前相等的俩个元素，排序后相对位置不变。
归并排序是稳定的
