algorithm - 与合并排序相比，修改后的合并排序的运行时间？

Question

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

在图表中，假设我们考虑中间一行的数字(如果有人可以在此处发布图片会有所帮助)。如果我将算法修改为:

• 合并 38 和 27，然后按升序排列数字。 (27, 38)
• 将上面的结果与 43 合并，然后按升序对数字进行排序。 (27, 38, 43)
• 将上面的结果与 3 合并，然后按升序对数字进行排序。 (3、27、38、43)。
• ...等等，直到我有一个完全排序的列表。

这是一种极其低效的排序方式(我可以凭直觉判断——在最坏的情况下，添加的数字将与列表中的每个数字交换)尽管我不太确定它是如何比较的(就证明我的理由而言)分析)到合并排序的 O(n log n) 时间。

有什么想法吗？

Answer 1

您描述的算法是插入排序 - 您通过一次添加一个元素来构建一个按排序顺序增长的值列表。这意味着运行时匹配插入排序 - 如果数组已排序则为线性，平均为二次，等等。