TimSort：用于识别给定单个块内自然运行的最佳算法

Question

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

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.

问题：

对于给定的大小块，Tim 排序实际上是执行 (A) 还是 (B) [ 例如：- 32 到 64 项]。即，直到满足块大小，它是否逐步识别每个项目并执行每个项目的 binaryInsertionSort 以构建排序的运行 ?

或

它是否首先扫描整个块以识别已经发生的自然排序的子序列以有效地合并它们？

Answer 1

TimSort : Optimal Algorithm for identifying natural runs within a given single block