1. 思想

将数组分割成一个一个有序的子数组，然后将子数组两两合并起来，形成一个新的有序数组

2. 算法

1. 先写一个函数用于分割数组，直到数组不可再分
2. 然后开始回溯合并子数组
3. 合并时先将左子数组和右子数组分别保存出来

4. 然后遍历整个左子数组和右子数组，判断四种情况：

   1. 左子数组遍历完，右子数组未遍历完
   2. 右子数组遍历完，左子数组未遍历完
   3. 左子数组头元素小于右子数组头元素，就将左子数组头元素放入外部数组
   4. 右子数组头元素小于等于左子数组头元素，就将右子数组头元素放入外部数组

3. 代码

参考视频：

• https://www.bilibili.com/video/BV1et411N7Ac?from=search&seid=7298375655374305648

private static void mergeSort(int[] array, int left, int right) {
    // 递归跳出条件
    if (left >= right) {
        return;
    }
    
    int middle = (left + right) >> 1;
    mergeSort(array, left, middle);
    mergeSort(array, middle + 1, right);
    merge(array, left, middle, right);
}

private static void merge(int[] array, int l, int m, int r) {
    
    int[] leftArray = new int[m - l + 1];
    int[] rightArray = new int[r - m];
    int leftHead = l;
    int rightHead = m + 1;
    
    // 填充左子数组
    for (int i = leftHead; i <= m; i++) {
        leftArray[i - leftHead] = array[i];
    }

    // 填充右子数组
    for (int i = rightHead; i <= r; i++) {
        rightArray[i - rightHead] = array[i];
    }

    // 注意要先判断子数组是否遍历完的情况
    for (int i = l; i <= r; i++) {
        // 左子数组遍历完，右子数组未遍历完
        if (leftHead > m && rightHead <= r) {
            array[i] = rightArray[rightHead - m - 1];
            rightHead++;
        // 右子数组遍历完，左子数组未遍历完
        } else if (rightHead > r && leftHead <= m) {
            array[i] = leftArray[leftHead - l];
            leftHead++;
        // 左子数组的头元素小于右子数组的头元素
        } else if (leftArray[leftHead - l] < rightArray[rightHead - m - 1]) {
            array[i] = leftArray[leftHead - l];
            leftHead++;
        // 右子数组的头元素小于左子数组的头元素
        } else if (rightArray[rightHead - m - 1] <= leftArray[leftHead - l]) {
            array[i] = rightArray[rightHead - m - 1];
            rightHead++;
        }
    }
}