I'm trying to recall what the expected level of clustering is even for properly random inputs.
A few years before Timsort there was someone randomly shuffling the input in order to avoid the reverse-order corner case that kills so many sort algorithms.
For truly random inputs, about half of the entries should be pairs that are partially ordered, and 25% runs of 3, no? And if memory serves Timsort also has a fast path for strictly decrementing runs as well, where it amortizes some of the comparisons done in the scan phase to do a blind reverse() call.
A few years before Timsort there was someone randomly shuffling the input in order to avoid the reverse-order corner case that kills so many sort algorithms.
For truly random inputs, about half of the entries should be pairs that are partially ordered, and 25% runs of 3, no? And if memory serves Timsort also has a fast path for strictly decrementing runs as well, where it amortizes some of the comparisons done in the scan phase to do a blind reverse() call.