Day 67：链表归并排序

我最开始是打算不在这个系列中谈及归并排序（mergesort）的。快速排序（quicksort）至少还算有意思，毕竟它操作起来有一定的技巧性。可是归并呢？归并有什么有意思的东西吗？其实是有的——计算模型就是。

对于给定数组的常规归并排序，时间复杂度是O(n*log n)，空间复杂度是O(n)。如果我们转而用链表方法会怎么样？

我分别用递归和迭代实现了这个算法。

递归版的算法使用了我们在Day 62里介绍的快/慢指针技巧，将列表拆分成了两个同样长度的部分，每个部分都已经经过排序，结果也已经合并。

该种算法的时间复杂度是O(n*log n)，空间复杂度是O(log n)。为什么空间复杂度不是O(1)呢？如果只对堆（heap）进行测算，复杂度确实是O(1)。但我们必须考虑到，调用递归本身也需要内存，所以空间复杂度是O(log n)而不是O(1)。

迭代版的算法会把长度为1的列表合并，然后不断将相同长度的列表合并，直到最终只剩下一个完整的列表。

该种算法的时间复杂度也是O(n*log n)，空间复杂度是O(log n)。

看起来用采用链表的算法（空间复杂度：O(log n)）似乎比采用固定数组的算法（空间复杂度：O(n)）更加节约内存，事实真的如此吗？

不见得。首先，链表这种数据结构本身就比固定数组更吃内存，不过这也让这种列表的信息容量更大。

归并排序可以利用链表结构的信息容量优势来避免进一步的内存消耗。上文中我们比较过栈与堆的区别，与此处情形类似。同样的要求依然存在，只不过不那么明显了。

准确地讲，链表归并排序需要额外分配O(log n)内存空间，但如果将保持这个排序所消耗的内存也考虑进去，那么总共需要的内存空间仍然是O(log n)。

算法实现

工具函数（Utilities）

测试

（原作者：Tomáš Bouda）