fn collapse(runs: &[Run]) -> Option<usize>Expand description
Examines the stack of runs and identifies the next pair of runs to merge. More specifically,
if Some(r) is returned, that means runs[r] and runs[r + 1] must be merged next. If the
algorithm should continue building a new run instead, None is returned.
TimSort is infamous for its buggy implementations, as described here: http://envisage-project.eu/timsort-specification-and-verification/
The gist of the story is: we must enforce the invariants on the top four runs on the stack. Enforcing them on just top three is not sufficient to ensure that the invariants will still hold for all runs in the stack.
This function correctly checks invariants for the top four runs. Additionally, if the top run starts at index 0, it will always demand a merge operation until the stack is fully collapsed, in order to complete the sort.