Timsort堆棧不變 - 爲什麼要儘可能延遲合併？

Question

我想了解Timsort算法，但我有以下執行堆棧不變的理由麻煩：

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

根據this文件，

我們想t o儘可能延遲合併以便利用稍後可能出現的模式，但是我們更希望儘快進行合併，以利用剛剛發現的運行在存儲器層級中仍然很高的運行。

我知道我們希望儘快合併以利用緩存效果，但我不明白爲什麼要延遲它的原因。他的意思是什麼「模式」？

Answer 1

這裏的模式是指被排序數據中的模式。例如，Timsort正在尋找數據中正在增加（或減少）的運行，這些運行或者已經排序，可以通過原地顛倒運行來輕鬆排序。然後它嘗試將這些運行用於其mergesort分區。

順便說一句，在Timsort維基百科的文章可能對你有用：https://en.wikipedia.org/wiki/Timsort