Follow-up: Merge Sort Implementation and Applications
Note
Now all the plugins has supported English. I'm still improving the website...
This article will resolve
| 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:
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.