拓展：归并排序详解及应用

315. 计算右侧小于当前元素的个数 https://leetcode.cn/problems/count-of-smaller-numbers-after-self

315. Count of Smaller Numbers After Self https://leetcode.com/problems/count-of-smaller-numbers-after-self

327. 区间和的个数 https://leetcode.cn/problems/count-of-range-sum

327. Count of Range Sum https://leetcode.com/problems/count-of-range-sum

493. 翻转对 https://leetcode.cn/problems/reverse-pairs

493. Reverse Pairs https://leetcode.com/problems/reverse-pairs

912. 排序数组 https://leetcode.cn/problems/sort-an-array

912. Sort an Array https://leetcode.com/problems/sort-an-array

Info

已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	Difficulty
315. Count of Smaller Numbers After Self	🔴
327. Count of Range Sum	🔴
493. Reverse Pairs	🔴
912. Sort an Array	🟠

Prerequisites

Before reading this article, you should learn:

• Basic Binary Tree Structure
• Binary Tree Traversal Framework
• Multiway Tree Structure and Traversal Framework
• Binary Tree Series Algorithms (Overview)

Many readers have requested that I explain basic sorting algorithms using a framework mindset. I think it's a great idea because understanding the essence of a concept deeply allows for more versatile application.

In this article, I'll start with merge sort, provide a code template, and then discuss its applications in algorithm problems. Before reading this, I hope you've read the previous article Hand-Holding Guide to Binary Trees (Overview).

When I discussed binary trees, I mentioned that merge sort is essentially a post-order traversal of a binary tree. Many readers found this revelation enlightening.

Do you know why many readers find recursive algorithms challenging? It's because they are still in the "seeing the mountain as a mountain, seeing the water as water" stage.

Take merge sort, for example. If you look at the code and try to visualize the process, what scene comes to mind?

Since it's an array sorting algorithm, do you imagine a GIF of an array with elements being swapped one by one? If so, your perspective is limited.

But if you envision a binary tree, or even the scene of a post-order traversal of a binary tree, your perspective is broader. Chances are, you've grasped the Framework Thinking that I often emphasize. Using this abstract ability makes learning algorithms much easier.

So, how is merge sort, an array algorithm, related to binary trees? Let's dive into the details.

Algorithm Approach

Code Implementation

Complexity Analysis

912. Sort an Array

315. Count of Smaller Numbers After Self

493. Reverse Pairs

327. Count of Range Sum

loading...