自顶向下和自底向上的区别？

Question

老师，你好，从我的理解来看，自顶向下的归并排序通过递归实现的过程中，递归返回操作也是从最底层开始merge的，也就是说递归到1个元素的时候开始向上返回，进而进行merge。那么这和直接自底向上的merge的具体区别在哪里呢？对这里没有太理解。

Answer 1

liuyubobobo 2017-07-23 12:57:05

首先一个主要区别在实现上。自顶向下的归并排序使用了递归的方式，而自底向上的归并排序只是迭代。所以自顶向下的归并排序过程使用了系统的栈空间。从这个角度，其实自底向上的归并排序性能更优。在这个课程的官方github中有对这两种方式性能的比较代码，虽然其实对现代计算机来讲，基本可以忽略递归带来的性能开销。

https://github.com/liuyubobobo/Play-with-Algorithms/tree/master/03-Sorting-Advance/Course%20Code%20(C%2B%2B)/Optional-02-MergeSort-and-MergeSortBU-Perfermance-Comparison

另一方面，自顶向下和自底向上，在归并的过程中，划分的数组是不一样的。自顶向下每次都平分数组；但是自底向上永远是以2的幂次的大小不断归并数组。

比如，对于有10个元素的数组，自顶向下的归并过程，先划分成5，5；对于5个元素的数组，划分为2，3；对于3个元素的数组，换分为1，2；对于2个元素，划分为1，1

但是，对于自底向上的归并排序，先划分为10个1，之后合并为5个2，之后合并为4，4，2，之后合并为8，2，最后合成10个元素有序的状态，可以看出，这个划分过程，是和自顶向下的归并过程不一样的。

• 提问者 charlenellll #1

  谢谢老师！