似乎在很多教科书中，自上而下的合并排序都是用数组完成的，因为它具有随机访问的优势。
我想知道是否有一种方法可以对其他数据结构进行归并排序？假设数据存储在队列或堆栈中，是否可以在队列/堆栈上最多与另一个辅助队列/堆栈进行合并排序？
我主要担心的是，既然没有随机访问，那么归并排序在这种情况下还能达到O(n logn)的效率吗？
最佳答案
将数组与归并排序一起使用的另一个优点是，如果您编写了巧妙(但难以理解)的算法，则可以在递归调用级别之间切换“临时”数组和“真实”数组。在任何有值(value)的合并排序实现中，只会分配一次“scratch”数组，但使用切换技术，您最多只需移动结果一次。
对于堆栈和队列，您可能无论如何都会使用数组作为底层数据结构。您可以使用链表，但是 push() 和 pop() 或 enqueue() 和 dequeue( ) 变大，因为您还必须为项目分配内存。显然，正如 @LearnedfromMistake 所示，使用堆栈和队列是可能的，但考虑到数组可能无论如何都被用作底层数据结构，尚不清楚这种方法的优势是什么.
关于algorithm - 合并排序与其他数据结构？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15452419/