我试图理解 Timsort 算法，但我无法理解实现堆栈不变性的原因:
- A > B+C
- B > C
根据 this文档，
We would like to delay merging as long as possible in order to exploit patterns that may come up later, but we like even more to do merging as soon as possible to exploit that the run just found is still high in the memory hierarchy.
我知道我们想尽快进行合并以利用缓存效果，但我不明白我们为什么要延迟合并。他指的是什么“模式”？
最佳答案
这里的模式指的是被排序数据中的模式。例如，Timsort 正在寻找数据中增加(或减少)的运行，这些运行要么已经排序，要么可以通过就地反转运行来简单地排序。然后它会尝试将这些运行用于其合并排序分区。
顺便说一下，关于 Timsort 的维基百科文章可能对您有用:https://en.wikipedia.org/wiki/Timsort
关于python - Timsort 堆栈不变 - 为什么要尽可能延迟合并？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10908783/