在部分排序的數組中插入如何比mergesort更好？

Question

我必須開發一種算法，它能夠對第一個（n-根（n））元素進行排序的n元素列表進行排序。是的，這是一個家庭作業問題。

在互聯網上有一些research和stack-overflow後，我相信插入排序和冒泡排序對部分排序的數組最有效。這link清楚地表明，插入排序比合並排序更好。我已經把插入排序作爲我家庭作業的答案。

但是，當我開始做漸近複雜度分析時，我感到困惑。

對於插入排序，我們至少要看看每個元素。如果元素未排序，我們將不得不進行移位/反轉。因此，插入排序將有O（n + m），其中m是總倒數。或者，我們也可以說它具有線性複雜度O（n）。

對於合併排序，我們需要對未排序的root（n）元素進行mergesort，這會給root（n）log（root（n））複雜度。此外，我們需要合併排序列表（這將採取O（n））。因此，由於n支配根（n）log（root（n）），所以複雜度將是O（root（n）log（root（n））+ n）或O（n）。

兩者如何都具有相同的漸近複雜性？這只是我的好奇心。在計算複雜度的過程中，我可能確實犯了錯誤。

我是一名學生，仍在學習。我感謝任何幫助。謝謝。

Answer 1

該列表中的總反轉計數可以高達（n-Sqrt（n））* Sqrt（n）= O（n ^3/2）。例如：100個元素列表（10 11 12..99 100 1 2 3 4 5 6 7 8 9 10）的倒置計數爲900，因此插入排序將執行大約900次操作（每個尾部元素90個移位）