mergesort计数比较

Question

我通过Python做了mergesort，它工作正常。我需要计算比较，当这种合并排序正在运行。我声明全局变量'merge_compare_count'，因为这是递归函数。我使用随机数列表A的元素。

但问题是，每当我运行这段代码时，我总是得到相同的merge_compare_count。我不知道为什么....

例如，当A获得了5000个随机不同的元素，但merge_compare_count总是123616.

任何帮助将欣赏返回相同的！

Answer 1

这不是问题。写它的方式，你的代码只有一个确定的步骤数量，只取决于大小，而不取决于数值。你甚至可以像这样计算它们：

>>> def f(n): 
     return 0 if n < 2 else f(n/2) + f(n-n/2) + 2*n 

>>> f(5000) 
123616