algorithm - 合并排序的最佳案例

Question

我已经制作了一个程序来计算不同 n 值的合并排序算法的成本，我已经采用了成本变量，并且每次遇到循环或条件检查时我都会递增它，当我得到排序的数组时我给它排序数组输入和输入再次合并排序，之后在第三种情况下我正在反转排序的数组所以这将是最坏的情况但是对于所有三种情况我得到相同的成本，那么合并排序的最佳和最坏情况是什么。

Answer 1

传统上作为自上而下递归函数或使用小型局部指针数组的自下而上迭代实现的合并排序的成本是相同的:O(N.log(N)) .比较次数将根据数组的实际内容而有所不同，但最多为 2 倍。

您可以通过在合并阶段添加左切片的最后一个元素和右切片的第一个元素之间的初始比较，以线性成本改进此算法。如果比较结果为 <=那么你可以跳过这对切片的合并阶段。

通过此修改，完全排序的数组排序速度更快，具有线性复杂度，使其成为最佳情况，部分排序的数组也会表现得更好。