Timsort stack invant - Why do you want to hold back the merge as long as possible?

Question

I am trying to understand the Timsort algorithm, but I am having trouble implementing the stack invariant:

• A> B + C
• B> c

According to this document,

We would like to restrain the merge as long as possible in order to use patterns that may arise later, but we like to make the merge as quickly as possible in order to use the fact that the just found start is still high in the memory hierarchy.

I understand that we want to merge as soon as possible in order to use the cache effect, but I do not understand the reason why we want to postpone it. What “patterns” does he mean by this?

Answer 1

Patterns here refer to patterns in sortable data. For example, Timsort searches for increasing (or decreasing) runs in data that are either already sorted or can be sorted trivially by changing the space in place. He then tries to use these runs for his merge sections.

By the way, the Wikipedia article about Timsort may be useful to you: https://en.wikipedia.org/wiki/Timsort