我讀出了問題破解編碼訪談，作者描述瞭解決方案，在標題中描述的問題如下：歸併堆棧（僅使用額外的堆棧，但許多需要）
通過合併排序解決方案，我們將創建兩個額外的堆棧並將堆棧分成兩個堆棧。 >零件。我們將遞歸地對每個堆棧進行排序，然後按排序順序將它們合併回原始堆棧。請注意，這需要爲每個遞歸級別創建兩個附加堆棧。
我想了解時間複雜性。我假設（儘管可能是完全錯誤的），需要兩個額外的堆棧，因爲當從上到下將兩個堆棧以自下而上的順序合併時，我們必須反覆從兩個堆棧中最小的元素彈出到堆棧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的冪次）或多相友好（斐波那契數）。