подсчеты сравнения в mergesort

Question

Я сделал mergesort Python и работает нормально. И мне нужно подсчитать сравнения, когда эта сортировка слияния запущена. Я объявляю глобальную переменную merge_compare_count, потому что это рекурсивная функция. И я использую случайные числа для элементов списка A.

Но проблема в том, что всякий раз, когда я запускаю этот код, у меня всегда был такой же merge_compare_count. Я не знаю, почему ....

Например, когда А получил 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