我读出了问题破解编码访谈，作者描述了解决方案，在标题中描述的问题如下：归并堆栈（仅使用额外的堆栈，但许多需要）
通过合并排序解决方案，我们将创建两个额外的堆栈并将堆栈分成两个堆栈。 >零件。我们将递归地对每个堆栈进行排序，然后按排序顺序将它们合并回原始堆栈。请注意，这需要为每个递归级别创建两个附加堆栈。
我想了解时间复杂性。我假设（尽管可能是完全错误的），需要两个额外的堆栈，因为当从上到下将两个堆栈以自下而上的顺序合并时，我们必须反复从两个堆栈中最小的元素弹出到堆栈2中，然后弹出堆栈2中的所有堆栈进入堆栈1以获得所有元素的升序。这个过程对于每一个递归级别都是O（N），并且由于我们递归地操作了一半，它会是O（logN）级别......正确吗？那么这是一个O（NlogN）时间算法吗？而O（N）空间复杂？
首先请注意，每个创建的堆栈都是，一半是父堆栈的大小。每个递归级别的堆栈大小总和为N.这给你的空间复杂度为O（N log N）。
但是，您可以做得更好。如果您在将每个堆栈拆分为两个（在下一个路径中）并且在合并它们（在途中）时回收这些子堆栈，那么您确实可以将空间保持为O（N）。
使用4堆栈和自下而上合并排序会更快。调用堆栈A，B，C和D，数据最初在堆栈A上（B，C，D为空）。将元素（弹出/推送）从A交替分解为C和D（1个元素到C，1个元素到D，...）。然后合并C和D的运行，交替A和B之间的合并运行输出（第一次传递2个元素到A，2个元素到B，...）。然后合并A和B的运行，交替输出到C和D（第二遍，4个元素到C，4个元素到D，...）。重复这个过程，直到只有一个排序的运行。比较的意义在每次“通过”时反转（C，D→A，B颠倒，A→B→C，D不颠倒）。 B，C，D的大小需要与A相同，除非堆栈是使用单个链接列表实现的。 4个FIFO队列可以使用相同的逻辑，但比较意义永远不需要颠倒。
对于3栈底向上合并排序，最初调用栈A，B，C，与该数据上A，（B，C是空的）。将A中的元素（弹出/推送）交替分解为B和C.然后将B中的元素与C中的元素合并，并将结果推送到A中，从而导致A中大小为2的分类运行。然后再次分割A ，这次只是在将两个元素从A移动到B并将两个元素从A移动到C之间交替。然后将大小为2的“运行”从B和C合并回A，从而创建大小为4的运行。由于该元素被推送当从A移动到B或C时，需要颠倒比较的意义，例如使用>替换< =对于升序（或原始顺序，如果相等）排序。 B，C的大小需要与A相同，除非堆栈是使用单个链接列表实现的。这是大约两倍的4堆栈版本作为缓慢的，因为之后的每个合并通，该数据必须被从A重新分配给B和C
对于3堆排序，自下而上合并的变化所谓的多相合并排序是最快的方法，因为它只需要一次分配，但多相3堆排序很复杂。 3栈多相合并排序几乎与4栈定期自下而上合并排序一样快。哪个更快取决于元素的数量是否合并（2的幂次）或多相友好（斐波那契数）。