python - Timsort 堆栈不变 - 为什么要尽可能长时间地延迟合并？

Question

我正在尝试理解 Timsort 算法，但是由于实现堆栈不变量的原因，我遇到了麻烦：

1. A > B+C
2. B > C

根据这份文件，

我们希望尽可能长时间地延迟合并，以便利用以后可能出现的模式，但我们更希望尽快进行合并，以利用刚刚找到的运行在内存层次结构中仍然很高。

我知道我们希望尽快进行合并以利用缓存效应，但我不明白我们为什么要延迟它的原因。他所说的“模式”是什么意思？

Answer 1

这里的模式是指被排序的数据中的模式。例如，Timsort 正在寻找数据中增加（或减少）的运行，这些运行要么已经排序，要么可以通过在原地反转运行来轻松排序。然后它尝试将这些运行用于它的归并排序分区。

顺便说一句，关于 Timsort 的维基百科文章可能对您有用：https ://en.wikipedia.org/wiki/Timsort