是否有一种仅使用堆栈对数据进行排序的有效方法（如果有帮助，则允许超过 2 个）？
我见过两种堆栈排序，但它们的时间复杂度为 O(n^2)。我想知道是否存在通过使用两个以上堆栈来实现时间复杂度 O(n log(n)) 的东西。
合并排序可以用3个栈来实现。一个简单的实现是在其他两个堆栈之间交替移动已排序的运行，然后将其他两个堆栈中的运行合并回原始堆栈。初始运行大小为 1 个元素。该代码需要跟踪运行大小。如果允许小型局部数组的空间复杂度为 O(1)，则可以使用插入排序来创建 16 到 64 个元素的小型运行。每个合并过程都会读取和写入每个元素两次，一次将排序的运行从原始堆栈移动到其他两个堆栈，一次将运行合并回来。这可以通过使用多相合并排序来改进，但它很复杂，因为初始分布最终的游程大小与斐波那契数相关，并且游程必须在升序和降序之间交替，以便最终合并将两个降序游程合并到一个堆栈，以最终堆栈中的升序数据结束。我在某个地方有代码，如果需要的话，我可以稍后添加到这个答案中。