基本思想
核心是分治，就是把一个复杂的问题分成两个或多个相同或相似的子问题，然后把子问题分成更小的子问题，直到子问题可以简单的直接求解，最原问题的解就是子问题解的合并。归并排序将分治的思想体现得淋漓尽致。
实现
一开始先把数组从中间划分成两个子数组，一直递归地把子数组划分成更小的子数组，直到子数组里面只有一个元素，才开始排序。
排序的方法就是按照大小顺序合并两个元素，接着依次按照递归的返回顺序，不断地合并排好序的子数组，直到最后把整个数组的顺序排好。
代码示例
package sort;
import java.util.Arrays;
/**
* @since 2019/10/19 11:13
*/
public class MergeSort {
public static void main(String[] args) {
int[] nums = {0, -2, -3, 111, 2, 3, 90};
sort(nums);
System.out.println(Arrays.toString(nums));
}
public static void sort(int[] nums) {
int[] temp = new int[nums.length]; //temp数组用于存放排序的元素
sort(nums, 0, nums.length - 1, temp);
}
public static void sort(int[] nums, int left, int right, int[] temp) {
if (left < right) {
int mid = left + (right - left) / 2;
sort(nums, left, mid, temp); //左半部分排序
sort(nums, mid + 1, right, temp); //右半部分排序
merge(nums, left, mid, right, temp); //合并两个部分的结果
}
}
public static int[] merge(int[] nums, int left, int mid, int right, int[] temp) {
int i = left; //左半部分索引位置
int j = mid + 1; //右边部分索引位置
int k = 0; //temp数组索引位置
while (i <= mid && j <= right) {
if (nums[i] < nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
while (i <= mid) {
temp[k++] = nums[i++];
}
while (j <= right) {
temp[k++] = nums[j++];
}
k = 0;
while (left <= right) { //从temp数组copy已经排好序的元素到原数组
nums[left++] = temp[k++];
}
return nums;
}
}
解题思路
算法分析
空间复杂度
由于合并 n 个元素需要分配一个大小为 n 的额外数组，合并完成之后，这个数组的空间就会被释放，所以算法的空间复杂度就是 O(n)。归并排序也是稳定的排序算法。
时间复杂度
归并算法是一个不断递归的过程。
举例：数组的元素个数是 n，时间复杂度是 T(n) 的函数。
解法：把这个规模为 n 的问题分成两个规模分别为 n/2 的子问题，每个子问题的时间复杂度就是 T(n/2)，那么两个子问题的复杂度就是 2×T(n/2)。当两个子问题都得到了解决，即两个子数组都排好了序，需要将它们合并，一共有 n 个元素，每次都要进行最多 n-1 次的比较，所以合并的复杂度是 O(n)。由此我们得到了递归复杂度公式：T(n) = 2×T(n/2) + O(n)。
对于公式求解，不断地把一个规模为 n 的问题分解成规模为 n/2 的问题，一直分解到规模大小为 1。如果 n 等于 2，只需要分一次；如果 n 等于 4，需要分 2 次。这里的次数是按照规模大小的变化分类的。
以此类推，对于规模为 n 的问题，一共要进行 log(n) 层的大小切分。在每一层里，我们都要进行合并，所涉及到的元素其实就是数组里的所有元素，因此，每一层的合并复杂度都是 O(n)，所以整体的复杂度就是 O(nlogn)。
