← RoseCode

ROSECODE 037

归并排序中的比较次数

Comparisons in Mergesort

elasolova · 编程 ·

归并排序是一种递归排序算法,定义为:
-假设输入的长度(n)是2的幂
-如果n=1,则返回该元素
-如果n>1,则将列表分成两部分
-对每一半调用归并排序
- 合并排序后的列表

使用归并排序对具有 2^150 元素的列表进行排序需要多少次比较(在最坏的情况下)?