我一直试图找出这个问题的答案而没有成功也许你可以引导我一点：我们改变合并排序，这样当你已经对数组进行排序时它会停止并返回数组，而不会调用另外2个递归调用。例如，让我们在一个数组上运行算法，数组中的每个数字都恰好是n / log（n）次，（这样数组中包含完全不同的数字log（n））现在的运行时间复杂度是多少？
“我们更改了合并排序，这样当你已经对数组进行排序时，它会停止并返回数组，而不会调用另外两个递归调用。”
这就是普通合并排序的工作原理。在对数组（或数组的一部分）进行排序之后，它不再调用任何递归调用，它只返回已排序的数组。调用递归是为了首先对数组的部分进行排序。
也许你想说“在我们递归排序两半并合并它们之前，我们检查数组是否已经排序”。对于具有不同数字的数组，这将是无用的，因为数组将被排序的机会极低（1/n!）。
在你的例子中它更有趣，但是如果数组只有log(n)不同的数字我会建议排序唯一值并创建一个从值到索引的散列图，这只是在log(n)值快速，然后你可以用桶来排序线性时间例如，排序。
实际上，您可以通过检查已排序的子数组是否已按正确顺序排序并跳过合并阶段来尝试提高排序数组的mergesort效率。这可以通过比较左子阵列的最后一个元素A对于右子阵列的第一个元素B来有效地完成。如果A <= B，不需要合并。
这个技巧不会增加复杂性，因为它为每个合并阶段添加了一个测试，但是它不会删除任何递归调用，因为它需要对两个子数组进行排序。相反，如果对数组进行排序，它确实会将复杂性降低到线性。
另一种方法是在拆分和递归之前检查数组是否已经排序。这在一般情况下增加了更多的测试，但是由于这个测试数量也受N log（N）的限制，因此不会增加复杂性。对于未排序的数组（更多的额外比较），它平均更昂贵，但在排序数组上更高效（相同数量的测试，但没有递归）。
您可以尝试在各种测试用例和数组大小上对这两种方法进行基准测试，以衡量影响。