归并排序, 元素比较次数与元素的初始排列有无关系？

Question

如题所述

Answer 1

楼上的不准确，虽然时间复杂度一致，但是元素的比较次数最好和最坏相差接近2倍：
假设递增排序，如果两个都是n个元素的有序序列合并，最少比较次数为n，此时是一个序列所有元素都比另外的第一个元素小，但是最多比较次数是2n-1，正好是两者的完全交错