归并排序

[hunterhug]

https://hunterhug.github.io/goa.c/#/algorithm/sort/merge_sort

Description

[baici1]

你在自底而上归并排序里面对于空间复杂度的分析有问题！
从你的描述中感觉空间复杂度只和函数递归栈有关，但是你的算法中用到一个N长度的辅助数组，其实我觉得空间复杂度为O(N)。
这是我的看法。

[baici1]

那个手摇算法在leetcode上面使用，我觉得可以填上去。
题目：剑指Offer58-II.左旋转字符串
leetcode 还是有用的！哈哈哈哈哈哈

[hunterhug]

@baici1
你在自底而上归并排序里面对于空间复杂度的分析有问题！
从你的描述中感觉空间复杂度只和函数递归栈有关，但是你的算法中用到一个N长度的辅助数组，其实我觉得空间复杂度为O(N)。
这是我的看法。

文章下面的手摇算法就节省了辅助数组的空间。如果没有原地排序，你确实可以说空间复杂度是O(N)，但是根据上下文，我们讨论的是两种方法的区别，空间上的复杂度只要考虑的是递归，自顶向下空间复杂度更大。

[hunterhug]

@baici1
那个手摇算法在leetcode上面使用，我觉得可以填上去。
题目：剑指Offer58-II.左旋转字符串
leetcode 还是有用的！哈哈哈哈哈哈

实际上，不是leetcode有用，你要明白这一点。