與合併排序相比，修改的合併排序的運行時間？

Question

來自維基百科，https://en.wikipedia.org/wiki/Merge_algorithm#Application

在圖中，我們假設我們考慮中間一行數字（如果有人可以在這裏發佈圖片會有所幫助）。如果我將其修改爲：

• 合併38和27，然後按升序對數字進行排序。 （27,38）
• 將上面的結果與43合併，然後按升序對數字進行排序。 （27,38,43）
• 將上面的結果與3合併，然後按升序對數字進行排序。 （3,27,38,43）。
• ...等等，直到我有一個完全排序的列表。

這是排序（我可以直觀地告訴我們 - 在被添加的數量將與列表中的每個數字交換最壞的情況下）一個非常低效的方式雖然我不能肯定它是如何比較（以條款證明我的分析合理）到合併排序的O（n日誌n）時間。

有什麼想法？

Answer 1

您正在描述的算法是插入排序 - 您正在按排序次序構建一個增長的值列表，方法是一次添加一個元素。這意味着運行時匹配插入排序 - 如果數組已排序，平均值爲二次等，則爲線性。