Сортировка по ключу против cmp_to_key: где решение проседает по времени

# A
def version_key(s):
    return tuple(int(p) for p in s.split("."))
result = sorted(versions, key=version_key)

# B
from functools import cmp_to_key
def compare(x, y):
    a = [int(p) for p in x.split(".")]
    b = [int(p) for p in y.split(".")]
    return (a > b) - (a < b)
result = sorted(versions, key=cmp_to_key(compare))

• `cmp_to_key` отключает Timsort и переключает сортировку на пузырьковую, из-за чего вместо O(n log n) получается O(n^2) сравнений — это и даёт замедление на миллионе строк
• B медленнее исключительно из-за создания объектов-обёрток `cmp_to_key`, по одной на элемент; разбор строк в обоих вариантах выполняется одинаковое число раз — ровно по разу на элемент
• В A ключ вычисляется один раз на элемент — n вызовов; в B разбор строк идёт внутри каждого сравнения, то есть порядка n log n раз, плюс вызов Python-функции на каждое сравнение вместо сравнения кортежей на уровне C
• В A ключ вычисляется заново при каждом сравнении, а в B обёртка кеширует уже разобранную версию строки, поэтому B обязан быть быстрее и наблюдаемое замедление объясняется погрешностью замера