归并排序是一种数组算法，它和二叉树有什么关系呢？

组合排序。如果我向您展示代码并要求您想象合并排序过程，您会想到什么场景？

这是一种数组排序算法，所以想象一下数组的 GIF 逐一交换元素？如果是这样，则图案很浅。

但是如果你想到二叉树，甚至是二叉树的后序遍历，模式就很高，你掌握框架的概率就很大。这种抽象能力使得学习算法变得更加容易。 。

那么归并排序明明是数组算法，和二叉树有什么关系呢？接下来我就详细的讲一下。

算法思路

我们这样期待吧，所有的递归算法，无论做什么，本质上都是遍历（递归）树，然后在节点（前序、中序、后序位置）运行代码，你必须编写递归算法，它基本上告诉每个节点要做什么。

看一下归并排序代码框架：

// 定义：排序 nums[lo..hi]
void sort(int[] nums, int lo, int hi) {
    if (lo == hi) {
        return;
    }
    int mid = (lo + hi) / 2;
    // 利用定义，排序 nums[lo..mid]
    sort(nums, lo, mid);
    // 利用定义，排序 nums[mid+1..hi]
    sort(nums, mid + 1, hi);

    /****** 后序位置 ******/
    // 此时两部分子数组已经被排好序
    // 合并两个有序数组，使 nums[lo..hi] 有序
    merge(nums, lo, mid, hi);
    /*********************/
}

// 将有序数组 nums[lo..mid] 和有序数组 nums[mid+1..hi]
// 合并为有序数组 nums[lo..hi]
void merge(int[] nums, int lo, int mid, int hi);

看了这个框架，你就会明白经典总结：Merge时先对数组的左半部分进行排序，再对数组的右半部分进行排序，然后再进行Sort合并数字的两半。

上面的代码和二叉树的后序遍历非常相似：

/* 二叉树遍历框架 */
void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    traverse(root.left);
    traverse(root.right);
    /****** 后序位置 ******/
    print(root.val);
    /*********************/
}

再进一步考虑一下求二叉树最大深度的算法代码：

// 定义：输入根节点，返回这棵二叉树的最大深度
int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    // 利用定义，计算左右子树的最大深度
    int leftMax = maxDepth(root.left);
    int rightMax = maxDepth(root.right);
    // 整棵树的最大深度等于左右子树的最大深度取最大值，
    // 然后再加上根节点自己
    int res = Math.max(leftMax, rightMax) + 1;

    return res;
}

是不是更相似？

上一篇文章一步步刷二叉树（大纲）说二叉树问题可以分为两类思路，一类是遍历一次二叉树的思路，一类是遍历二叉树的思路。解决问题。根据上面的类比，很明显归并排序采用了问题的分解思想（分而治之算法）。

合并过程可以在逻辑上抽象为二叉树。树中每个节点的值可以被视为数字nums[lo..hi]。叶节点的值是数组中的一个元素。元素：

然后在每个节点顺序后面的地方执行merge操作（左右子节点已排序），将两个子节点中的子行合并：

这个merge操作在二叉树的每个节点执行一次，执行顺序为二叉树顺序之后的遍历。

二叉树的后序遍历大家应该都很熟悉了。就是下图中的遍历顺序：

结合上面的基本分析，我们将nums[lo..hi]理解为二叉树节点，srot函数理解为二元树的遍历函数。整个归并排序的执行过程如下GIF所示：

这样，归并排序的核心思想就分析完了。接下来，只需将想法转化为代码即可。

代码实现与分析

只要你有正确的思维方式，理解算法思想并不难，但是将思想实现到代码中也考验你的编程能力。

算法的时间复杂度毕竟只是一个理论上的衡量，算法实际运行效率需要考虑的因素更多。例如，避免频繁的内存分配和释放、代码逻辑尽可能简洁等等。

经过比较，《算法 4》给出的归并排序代码既简洁又高效，因此我们可以参考书上给出的代码作为合并算法的模型：

class Merge {

    // 用于辅助合并有序数组
    private static int[] temp;

    public static void sort(int[] nums) {
        // 先给辅助数组开辟内存空间
        temp = new int[nums.length];
        // 排序整个数组（原地修改）
        sort(nums, 0, nums.length - 1);
    }

    // 定义：将子数组 nums[lo..hi] 进行排序
    private static void sort(int[] nums, int lo, int hi) {
        if (lo == hi) {
            // 单个元素不用排序
            return;
        }
        // 这样写是为了防止溢出，效果等同于 (hi + lo) / 2
        int mid = lo + (hi - lo) / 2;
        // 先对左半部分数组 nums[lo..mid] 排序
        sort(nums, lo, mid);
        // 再对右半部分数组 nums[mid+1..hi] 排序
        sort(nums, mid + 1, hi);
        // 将两部分有序数组合并成一个有序数组
        merge(nums, lo, mid, hi);
    }

    // 将 nums[lo..mid] 和 nums[mid+1..hi] 这两个有序数组合并成一个有序数组
    private static void merge(int[] nums, int lo, int mid, int hi) {
        // 先把 nums[lo..hi] 复制到辅助数组中
        // 以便合并后的结果能够直接存入 nums
        for (int i = lo; i <= hi; i++) {
            temp[i] = nums[i];
        }

        // 数组双指针技巧，合并两个有序数组
        int i = lo, j = mid + 1;
        for (int p = lo; p <= hi; p++) {
            if (i == mid + 1) {
                // 左半边数组已全部被合并
                nums
 = temp[j++];
            } else if (j == hi + 1) {
                // 右半边数组已全部被合并
                nums
 = temp[i++];
            } else if (temp[i] > temp[j]) {
                nums
 = temp[j++];
            } else {
                nums
 = temp[i++];
            }
        }
    }
}

与前面的例子一样，这里我们只需要关注这个连接到的函数即可。

sort 函数对 nums[lo..mid] 和 nums[keski+1..hi] 尚未重新运行。为了把两者连接起来，所以需要将其复制到 temp 数组中，然后使用类似于上一篇文章《单向链表的六种技巧》的双指针技术来连接有序的一。链接列表 nums[lo..hi]合并到有序表中：

请注意，当 mergemerge 是新的时，我们不会更新辅助表。 temp提前帮助表以避免在递归中重复分配和释放内存可能引起的性能问题。

我们来谈谈归并排序的时间复杂度。虽然每个人都应该知道它是O(NlogN)，但并不是每个人都知道如何计算这个复杂度。

在之前的文章《动态规划详解》中提到，递归算法的复杂度计算是子问题的数量 x 求解子问题的复杂度。

在联合排序中，相当多的复杂性显然集中在join函数执行nums[lo..hi]

的过程，但每次

、 输入 lo 和 hi 都是不同的，因此直观地看到时间的复杂性并不容易。

merge执行了多少次？每次执行的时间复杂度是多少？总时间复杂度是多少？这个必须结合之前画的图来看：

执行次数就是二叉树节点的数量，每次执行的复杂度就是每个节点所代表的子表的长度，所以总的时间复杂度就是整棵树中“矩阵元素”的数量。

所以总体来说，这棵二叉树的高度是logN，其中每一层的元素数量就是原数组的长度N，即总时间复杂度。 O(NlogN)。

912。问题“Sort Array”是让你对数组进行排序。我们可以直接使用归并排序代码模型：

class Solution {
    public int[] sortArray(int[] nums) {
        // 归并排序对数组进行原地排序
        Merge.sort(nums);
        return nums;
    }
}

class Merge {
    // 见上文
}

其他应用

除了最常见的排序问题之外，归并排序还可以用来解决李口的问题315“统计右边元素的个数小于当前元素”：

我不是在谈论一个让我头疼的暴力解决方案，嵌套循环，二次复杂度。

这个问题和组合物种有什么关系？主要取决于merge函数。当我们连接两个有序数组时，我们实际上可以知道数字x中有多少位数字小于x。

尤其是这个场景：

此时我们应该将 temp[i] 放在 nums

/* 二叉树遍历框架 */
void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    traverse(root.left);
    traverse(root.right);
    /****** 后序位置 ******/
    print(root.val);
    /*********************/
}

nums

因为