关于二路归并排序,趟数的问题!
发布网友
发布时间：2023-12-22 16:40
共1个回答
热心网友
时间：2024-03-20 11:15
首先是二路归并排序，多路另说。
第二，趟数说的是非递归二路归并排序，递归的另说。
一趟排序最多可以排两个数据，即左边一个单元和右边一个单元归并到一个单元中。
两趟排序最多可以排四个数据，即一趟排好的两个单元归并到一个单元中。
……
……
k趟排序最多可以排2的k次方个元素。
k趟排序最少可以排2的（k-1）次方个元素。
假设要排n个元素，则
2^(k-1) < n <=2^k
解得 k-1< log n <=k
即为 log n 往上取整
如下
