I've been trying to implement timsort with the powersort merging strategy. The problem I'm having is that I can't figure out how the conditions required by merge_hi and merge_lo is upheld even when looking at the code. merge_lo and _hi states that:

... Must also have that ssa.keys[na-1] belongs at the end of the merge, ...

and if you look at the official java implementation which seems even more restrictive, it states:

The first element of the first run must be greater than the first element of the second run (a[base1] > a[base2]), and the last element of the first run (a[base1 + len1-1]) must be greater than all elements of the second run.

The java implementation does not use powersort though.

Any one with some experience with these algorithm that can give some insight?