Merge Sort and Binary Tree Postorder
Prerequisite Knowledge
Before reading this article, you should first learn:
Summary in One Sentence
The core idea of merge sort needs to be understood in conjunction with Post-Order Traversal of Binary Trees: first, use recursion to sort the left and right subarrays, then merge the two sorted arrays at the post-order position of the binary tree.
Considering this is a basic knowledge section, I will only discuss the overall idea of merge sort. The detailed code implementation and algorithm application will be covered in Detailed Explanation and Application of Merge Sort after the binary tree section. It is not recommended for beginners to read it now.
Since the merge sort algorithm requires a good grasp of recursive thinking and the use of the Two-Pointer Technique to merge two sorted arrays, it is advisable for beginners to learn in the order of the site's directory. This will make it easier to understand the code for merge sort eventually.
Core Idea of Merge Sort
Although the opening summary is rather abstract, with the foundation laid in the previous chapter on Core Idea of Quick Sort, you should have some sense of it.
I will compare it with the idea of quick sort to help you clearly see the difference:
The idea of quick sort, as mentioned earlier, is to first place an element in the correct position (sorted), and then recursively sort the remaining elements to the left and right of this element. Eventually, the entire array is sorted. The code framework is as follows: