算法学习笔记----归并排序(三)

归并排序的空间复杂度为Θ(n)。这个空间复杂度有些疑问，网上看到这样的解释“由于归并排序在归并过程中需要与原始记录序列同样数量的存储空间存放归并结果以及递归时深度为log2n的栈空间，因此空间复杂度为O(n+logn)”，但是感觉这个解释说不通。我是这样理解的，递归就是要高度抽象，在递归式中对左半部和右半部分别排序看作一个过程，真正要考虑的空间是在对左半部和右半部排序之后合并时需要的空间，因此空间复杂度为Θ(n)。这个理解很是牵强,,,,,