似乎在很多教科书中，自上而下的合并排序是使用数组完成的，因为数组具有随机访问的优势。
我想知道是否有办法与其他数据结构进行合并排序？假设数据存储在队列或堆栈中，是否可以在队列/堆栈上与最多的另一个辅助队列/堆栈进行合并排序？
我主要担心的是，由于没有随机访问，在这种情况下合并排序是否仍然能够达到O（n logn）效率？
最佳答案
使用带合并排序的数组的另一个优点是，如果编写了聪明（但不可理解）的算法，则可以在递归调用级别之间切换“scratch”数组和“real”数组。在merge sort的任何实现中，worth its salt只分配一次“scratch”数组，但是使用交换技术，最多只需移动一次结果。
对于堆栈和队列，您很可能将数组用作底层数据结构您可以使用链表，但随后push()和pop()或enqueue()和dequeue()中的常量因子会变大，因为您还必须为项目分配内存。显然，正如@learnedfromerror所示，使用堆栈和队列是可能的，但是考虑到数组可能被用作底层数据结构，不清楚这种方法的优势是什么。