解构算法中的归并排序

剖析算法领域的归并排序

算法系列之七：归并排序

一、归并排序的递归探究

1. 思路解析

期望的结果能够通过将整体拆解为子部分的表达式来呈现。

• 快速排序思路类比：
  整体有序状态可看作某一元素有序，且其左右断开的数组均有序。
• 归并排序思路：
  整体有序是左断开数组有序、右断开数组有序，再将两个有序数组合并为一个有序数组的结果。

2. 构建过程

2.1 处理不符条件情况（底层场景）

• 若数组为空（array == null），直接返回，无需排序；
• 若左右指针重合（left == right），说明仅有一个元素，本身有序，无需排序；
• 若左指针大于右指针（left > right），表明无法进行排序操作，直接返回。

2.2 基础排序验证（底层向上的中间层）

在底层向上的中间层，有序数组合并操作能够在底层实现两元素间的比较与排序。

2.3 结果回溯整合（向上回搭）

有序数组的结果会逐层向上回溯并整合，维持整体的有序状态。

3. 本质剖析

从底层的最小独立有序子数组开始，逐层向上有序合并，最终形成完整的有序数组。

4. 代码实现

public static void mergeSort(int[] array) {
    mergeSortFunc(array, 0, array.length - 1);
}

private static void mergeSortFunc(int[] array, int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;

    mergeSortFunc(array, left, mid);
    mergeSortFunc(array, mid + 1, right);
    merge(array, left, right, mid);
}

private static void merge(int[] array, int left, int right, int mid) {
    int s1 = left;
    int s2 = mid + 1;
    int[] tmpArr = new int[right - left + 1];
    int k = 0;
    // 两个区间均有数据时的比较合并
    while (s1 <= mid && s2 <= right) {
        if (array[s2] <= array[s1]) {
            tmpArr[k++] = array[s2++];
        } else {
            tmpArr[k++] = array[s1++];
        }
    }
    // 处理剩余元素
    while (s1 <= mid) {
        tmpArr[k++] = array[s1++];
    }
    while (s2 <= right) {
        tmpArr[k++] = array[s2++];
    }
    // 将临时数组结果放回原数组
    for (int i = 0; i < tmpArr.length; i++) {
        array[i + left] = tmpArr[i];
    }
}

二、递归的调用栈分析

1. 递归执行流程

在函数递归过程中，当前调用的函数会触发下一层函数的执行，直到形参满足终止条件才开始逐层返回，形成逐层深入后再逐层返回的过程。

2. 函数栈帧细节

每次函数调用都会独立创建栈帧并压入调用栈，函数执行完毕后栈帧弹出。递归调用时，栈帧按顺序压入，直到达到底层条件开始弹出，此时上层函数可能会根据新的形参继续递归调用，形成二叉树结构的执行流程：

2.1 递归函数栈帧压弹

归并排序的二叉树递归调用中：
- 每次向下递归到底层时，调用栈空间达到最大（深度为树的高度log(n)）；
- 向上返回时，上层函数会根据新形参再次递归，调用栈空间再次达到最大；
- 当右侧递归完成后，开始执行合并有序数组的操作。

2.2 合并有序数组函数栈帧压弹

执行合并有序数组函数时，会压入该函数的栈帧，其中包含临时数组空间。由于该函数无嵌套调用，压入后立即弹出，临时数组空间随层数变化。

三、归并排序的复杂度分析

1. 空间复杂度

空间复杂度关注整个执行过程中最大的瞬时占用空间。递归调用栈空间随层数递减，而合并有序数组的临时数组空间在最上层达到最大，因此归并排序的空间复杂度为O(n)。

2. 时间复杂度

时间复杂度通过分析每层合并操作的时间和得出。每层合并操作时间和为n，共有log(n)层，因此时间复杂度为O(n*log(n))