话说，merge sort的空间复杂度可以优化成 lg n 吗？

如题，假如每一层，我是in place的merge呢？

call stack每一个栈帧一定要O(n)而不是O(1)吗?

一共是lg n层

不可能，如果有log n的sort下一个图灵奖就是你的。我没有看懂为什么in place sort就能省掉一个n

补充内容 (2020-4-5 09:10):
哦哦，老夫眼瞎了，空间复杂度，不好意思楼主

补充内容 (2020-4-5 09:16):
但是in place merge sort会影响到时间复杂度，可能时间复杂度不再是nlogn

602689817 发表于 2020/04/06 00:08:31
不可能，如果有log n的sort下一个图灵奖就是你的。我没有看懂为什么in place sort就能省掉一个n

哦哦，老夫眼瞎了，空间复杂度。不好意思楼主

602689817 发表于 2020-4-6 00:10
哦哦，老夫眼瞎了，空间复杂度。不好意思楼主

哦哦没事 啊

线性时间的原地merge似乎是存在的：http://akira.ruc.dk/~keld/teachi ... kler/04/Huang88.pdf