mergesort_归并排序
2018-10-18 本文已影响0人
阿_贵
Top-down mergesort (recursive)
递归：1. 先切割成左右相等的部分，2. 排左面的部分，3. 排右面的部分，4. 再合并
Bottom-up mergesort (iterative)
迭代（循环）：1. 一个一个合并，2. 两个两个合并，3. 四个四个合并，4. 八个八个合并......
最好、平均、最坏时间复杂度都为：O(n*logn)
因为最后合并两个数组时，所用的辅助空间为n，所以空间复杂度为：O(n)
