[issue35369] List sorting makes duplicate comparisons

[David Wyde]

New submission from David Wyde <david.wyde at gmail.com>:

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.

----------
files: sort-fix.diff
keywords: patch
messages: 330839
nosy: dwyde, tim.peters
priority: normal
severity: normal
status: open
title: List sorting makes duplicate comparisons
type: performance
versions: Python 3.8
Added file: https://bugs.python.org/file47962/sort-fix.diff

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue35369>
_______________________________________