归并排序

基本思想
核心是分治，就是把一个复杂的问题分成两个或多个相同或相似的子问题，然后把子问题分成更小的子问题，直到子问题可以简单的直接求解。

实现
把数组从中间划分成两个子数组，一直递归地把子数组划分成更小的子数组，直到子数组里面只有一个元素，才开始合并排序。

分解左右并排序

左右两部分合并排序

Java代码

public void mergeSort(int[] nums, int left, int right) {
    if (left >= right) {
        return;
    }
    int middle = (left + right)/2;
    // 分化数组
    mergeSort(nums, left, middle);
    // 分化数组
    mergeSort(nums, middle+1, right);
    // 合并左右边
    merge(nums,left,middle,right);
}

// 合并排序好的左边和右边
public void merge(int[] nums, int left, int middle, int right) {
    //临时数组
    int[] tmp = new int[right-left+1];
    // start1 左边索引 start2右边索引 index 临时数组索引
    int start1 = left, start2 = middle + 1, index = 0;
    while (start1 <= middle || start2 <= right) {
        if (start1 > middle) {         // 左边已经排序完，只排序右边
            tmp[index++] = nums[start2++];
        } else if (start2 > right) {   //右边已经排序完，只排序左边
            tmp[index++] = nums[start1++];
        } else if (nums[start1] > nums[start2]) { //两边都没有排序完
            tmp[index++] = nums[start2++];
        } else {                                  //两边都没有排序完
            tmp[index++] = nums[start1++];
        }
    }
    //  把排序好的数据重新赋值回原数组中
    for (int i = left; i <= right; i++) {
        nums[i] = tmp[i-left];
    }
}

空间复杂度

由于合并 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)。

END!