https://i.imgur.com/5P19VRF.jpg
这题的B小题
为什么call merge sort的次数是2次
如果照下面那样做的话不是3次吗
另外想问quick sort是in place吗
洪逸上课笔记里写不是in place的是merge sort和非comparison base的排序
不过我看quick sort的空间复杂度是O(logn)~O(n)
所以不知道quick sort是不是in place
麻烦各位 谢谢

推F大

Quicksort 算不算 inplace 取决于你 inplace 的定义如果你定义 inplace 是最多只能用 O(1) 额外空间，那quicksort 就不是 in-place不过因为 quicksort 有一种版本可以最多只使用O(lg n)空间 所以很多人也认为 quicksort 是 in-place理论上 quicksort 可以只使用 O(1) 空间，只是方法很复杂所以教科书上也不会提

只有4,5 1,2算swap 剩下都是两个串行摆前后直接合并另外quick sort的空间复杂度是call递回stack的层数它依然是in-place