Python's Timsort sometimes makes the same comparison twice. This leads to extra compares, which can hurt performance.

Python sorts several length-3 permutations in 4 steps, and the problem accumulates with bigger data. There are ~9,800 duplicate less-than checks when sorting a million randomly ordered numbers, and 24,386 wasted comparisons when sorting all permutations of length 8.

I've attached a patch to fix this issue. Feedback and improvements are appreciated. Speed seems roughly comparable, and should be much improved for expensive comparison functions.

The same problem occurs in the Chromium Browser, and probably other ports of Python's Timsort implementation.