S7. 归并排序
如果要归并排序的个数为奇数,是否可行呢?
空间复杂度做不到 O(1) 吗?
做得到,但代价是理解以及实现上更大的复杂度。事实上归并排序的标准实现理解起来相当简单且优美,强榨空间复杂度的版本就不一样了。下面是一些相关的论文和参考资料,你要是感兴趣可以去读一下。
- 论文:Practical in-place mergesort
- stackoverflow:How to sort in-place using the merge sort algorithm
- 相关代码:mergesort.c