0

问题:在分块或生成块大小 [32-64 项] 的运行期间,timsort 如何识别最佳方法是搜索升序或降序运行?

Known Fact : A run in timsort is a natural occurring sorted order of data items [ either ascending or descending ].

示例:假设有一个块大小为 6 的数组进行排序。在提供的数据数组中遇到的一个 6 块如下所示。进一步假设数组是按升序排序的。

arr = {..............7, 11, 9, 6, 5, 2, ..................}. 

如果我们看到前两项 7、11 提供的提示,这是运行的增加子部分。在这一点上,考虑接下来的 4 项以确保我们维持或寻找增加的运行将是低效的,因为它实际上是一个递减的运行 [9, 6, 5, 2]。binaryInsertionSort 算法将按如下所示的递增顺序对其进行排序。

7

7、11

7、9、11

6、7、9、11

5、6、7、9、11

Result=2, 5, 6, 7, 9, 11---------(A)

事实上,最有效的方法是。

7, 11 -> 一次完整的上升运行。

9, 6, 5, 2 -> 一个完整的下降运行。

合并 ([ 7, 11 ], [9, 6, 5, 2])

merge([7, 11], [2, 5, 6, 9]) //就地反转第二个数组。

Result=2, 5, 6, 7, 9, 11 -------(B)

Fact: (B) is more efficient then (A) from computing perspective.

问题:

对于给定的大小块 [例如:- 32 到 64 个项目],Tim 排序实际上是否执行 (A) 或 (B)。即在满足块大小之前,它是否识别逐步查看每个项目并执行每个项目的 binaryInsertionSort 以构建排序的 Run ?

或者

它实际上是否首先扫描整个块以识别已经出现的自然排序子序列以有效地合并它们?

4

1 回答 1

0

它确实(A)。确定下一次运行,然后如果很短,则使用二进制插入排序对其进行扩展

于 2020-06-21T23:04:21.463 回答