合併排序基礎

Merge Sort 是一種分而治之的演算法。它將長度為 n 的輸入列表連續分成兩半，直到有 n 個大小為 1 的列表。然後，將列表對與每個步驟中新增的列表對中較小的第一個元素合併在一起。通過連續合併並通過比較第一元素，構建排序列表。

一個例子：

時間複雜性 ：T(n) = 2T(n/2) + Θ(n)

可以使用遞迴樹方法或主方法來解決上述重現。如果主法的情況 II，則復發的解決方案是Θ(nLogn)。時間的複雜性歸併排序在所有 3 個例（Θ(nLogn) 最差，平均和最佳 ）作為合併排序總是劃分陣列中的兩半，並採取線性時間合併兩半。

輔助空間 ：O(n)

演算法正規化 ：分而治之

就地排序 ：不在典型的實施中

穩定 ：是的