algorithm - 与其他数据结构合并排序？

Question

鉴于其随机访问的优势，似乎在许多教科书中自上而下的合并排序是使用数组完成的。

我想知道是否有办法与其他数据结构进行合并排序？假设数据存储在队列或堆栈中，是否可以在队列/堆栈上与最多另一个辅助队列/堆栈进行合并排序？

我主要担心的是，由于没有随机访问，在这种情况下合并排序仍然能够达到 O(n logn) 效率吗？

Answer 1

使用带有归并排序的数组的另一个优点是，如果您编写巧妙（但难以理解）的算法，您可以在递归调用级别之间切换“临时”数组和“真实”数组。在任何有价值的合并排序实现中，只会分配一次“临时”数组，但使用切换技术，您最多只需移动一次结果。

对于堆栈和队列，您可能会使用数组作为底层数据结构。您可以使用链表，但是push()和pop()或enqueue()和中的常数因子dequeue()会变大，因为您还必须为您的项目分配内存。显然，正如@LearnedfromMistake所示，使用堆栈和队列是可能的，但鉴于数组很可能被用作底层数据结构，尚不清楚这种方法的优势是什么。