归并排序

1、归并排序思想：

　　归并排序的思想源于一个简单的思想，就是如果现在存在两个已经排好序的数组了，例如：{2, 3, 6, 8, 11}，{1, 5, 7, 9}，那么对这两个排序好的数组进行合并排序，就比较简单了，只需要创建一个临时的辅助数组，然后比较两个数组的头元素，2比1，那就将1先存入辅助数组，并且右边的数组指针向后移动一位。再比较两个数组的指针指向的元素，2比5小，那么2存进临时数组。不断的比较指针指向的元素，不断的往临时数组中存入，即可得到合并后的排序数组。

　　基于这个思想，如果我们先把无序数组拆分成两个数组例如：{2, 3, 6, 8, 11, 1, 5, 7, 9,0}拆分成{2, 3, 6, 8, 11}，{1, 5, 7, 9,0}，若继续的进行拆分，直到所有的数组都拆分成了单个的元素即{2}{3}{6}{8}{11}{1}{5}{7}{9}{0}，变成了单个元素之后，就相当于这单个元素有序了。然后再合并，两个单个的合并成两个元素的，两个两个元素的合并成多个元素的，多个元素的最终合并成总的数组，这时候数组一定就排序完成了。

　　因此归并排序就是递归和分治思想的结合。

比如初始数组：[24,13,26,1,2,27,38,15]

①分成了两个大小相等的子数组：[24,13,26,1] [2,27,38,15]

②再划分成了四个大小相等的子数组：[24,13] [26,1] [2,27] [38,15]

③此时，left < right 还是成立，再分：[24] [13] [26] [1] [2] [27] [38] [15]

此时，有8个小数组，每个数组都可以视为有序的数组了！！！，每个数组中的left == right，从递归中返回(从19行--20行的代码中返回)，故开始执行合并(第21行)：

merge([24],[13]) 得到 [13,24]

merge([26],[1]) 得到[1,26]

.....

最终得到有序数组。

2、代码：

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {2, 3, 6, 8, 11, 1, 5, 7, 9,0};
        //先写merge，测试一下
        // merge(arr, 0, 4,7);
        //然后在拆分数组
        sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + ",");
        }
        System.out.println();

    }

    public static void sort(int[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    //拆分数组，最终的目的就是拆成一系列单个元素的数组,为了递归，函数参数为：数组左起始指针，右终止指针
    public static void sort(int arr[], int left, int right) {
        //递归终止条件，将数组分成了只有单个元素的时候停止
        if (left < right) {
            int mid = left + (right - left) / 2;
            sort(arr, left, mid);
            sort(arr, mid + 1, right);
            merge(arr, left, mid + 1, right);
        }
    }

    //合并两个有序数组
    //传参：待排序数组、左数组起始指针、右数组起始指针、右数组终止指针
    public static void merge(int arr[], int leftp, int rightp, int rightBound) {
        int mid = rightp - 1;
        int[] tempArr = new int[rightBound - leftp + 1];
        int i = leftp;
        int j = rightp;
        int k=0;
        while (i <= mid && j <= rightBound) {
            if (arr[i] <= arr[j]) {
                tempArr[k++] = arr[i++];
            } else {
                tempArr[k++] = arr[j++];
            }
        }
        while (i <= mid) {
            tempArr[k++] = arr[i++];
        }
        while (j <= rightBound) {
            tempArr[k++] = arr[j++];
        }
        //将临时数组的值赋给arr
        for (int m = 0; m < tempArr.length; m++) {
            arr[leftp + m] = tempArr[m];
        }
    }
}

3、时间空间复杂度：

时间复杂度为O(nlogn)，空间复杂度为O(n)

归并排序中，用到了一个临时数组，故空间复杂度为O(N)

由归并排序的递归公式：T(N) = 2T(N/2) + O(N) 可知时间复杂度为O(NlogN)

4、归并与快排比较：

　　归并更加稳定，当数据量很大的时候仍然可以保持较快的效率，但快排会变成最坏的情形O(n^2)

https://www.cnblogs.com/hapjin/p/5518921.html

https://blog.csdn.net/qq_36442947/article/details/81612870

视频讲解：https://www.bilibili.com/video/av48071817

https://www.bilibili.com/video/av48142871/?spm_id_from=333.788.videocard.0