归并排序将序列不分成两半

Question

通常，归并排序是将序列一分为二，递归排序。
但是，是否也可以通过将序列除以三分之一来执行归并排序？

mergesort(array, start, last) {
tri_mid = (start+last)/3;
mergesort(array, start, tri_mid);
mergesort(array, tri_mid+1, last);
merge(array, start, last);
}

这会起作用吗？
如果是，那么 bigO 表示法是什么？

Answer 1

是的，它肯定会起作用，但归并排序的优势在于递归分而治之的方法。如果每次将列表分成两半，那么您将得到 O(log2(n))，但由于计算复杂性的工作原理，这等效于 O(log n)。如果你把列表分成不相等的两部分，那么你的大O表达式仍然是O(log n)，因为你在每一层把列表分成几部分，但可能比把列表分成两半要慢，因为算法不会以最佳状态工作，即拆分列表，对每个部分进行排序，并合并已排序的子列表。作为思考的食物，想象一下如果合并排序只选择第一个项目作为左子列表，其他所有项目作为右子列表会发生什么。然后大 O 表达式将是 O(n^2)，这与其他更糟糕的算法一样糟糕。当然，如果你想尝试你的想法，就这样做，并计时!然后你会确切地知道什么是更快。