随机合并排序

Question

我在算法书中给出了以下问题:

假设实现了合并排序,以便在随机位置拆分文件,而不是恰好在中间.这种方法可以使用多少次比较来平均排序n个元素？

谢谢.

Answer 1

为了引导您找到答案，请考虑以下更具体的问题：

假设分割始终为 10%、25%、75% 或 90%。在每种情况下：对递归深度有什么影响？每个递归级别需要进行多少次比较？