0
Я решал проблему и сталкивался с этим решением, создавал упорядочение чисел с 1 по 8, что приведет к сортировке слияния, чтобы сделать наихудшее число сравнений 17.mergesort 17 сравнения с использованием 8 элементов
[7, 3, 5, 1, 8, 4, 6, 2], я решил это и произошло 16 сравнений, в соответствии с решением, это 17 сравнений? Любое объяснение будет оценено.
Я получил первые 2 (4 сравнения и 6 сравнений) правильно, но я до сих пор не уверен, как вы получите 7 в конце, я получил 6. Разум подробнее об этом? Я использую счетные инверсии. – Guy2016
Последний прогон объединяет два отсортированных прогона размером 4 для создания одного сортированного прогона 8. В худшем случае для каждого перемещенного элемента есть одно сравнение, за исключением последнего оставшегося элемента, который только что скопирован, так что это сравнение 7. – rcgldr