Слияние списков на python. Сравнение скорости

[PashaWNN]

По названию статьи подумал, что Хабр скатился совсем, но в итоге оказалось что я даже что-то новое узнал о питоне, хотя такого уже давно не было в принципе.
Грамотно и по сути.

[VADemon]

Можно было бы и полезть в кишочки, ожидаемо sort_merge это внутренняя реализация на C, а gen_merge/heapq_merge — примерный верх мечтаний для чистого Python кода; но это всё на усмотрение автора ;)
Мне было интереснее увидеть, что и тесты на скорость готовые есть (логично) и даже доки на 30к символов: github.com/python/cpython/blob/3.8/Objects/listsort.txt

Зацепился глаз за это:

This describes an adaptive, stable, natural mergesort, modestly called
timsort (hey, I earned it <wink>).

Коммит в 2002г. от «tim-one» — подозрительно, да? Вики:

Timsort is a hybrid stable sorting algorithm [...] It was implemented by Tim Peters in 2002 for use in the Python programming language.

∎

[igand]

Стоило бы тогда ещё сравнить функции sort() и sorted(). Я для интереса попробовал — разница заметная получилась:

list1 = [i for i in range(1, 200000, 3)]
list2 = [i for i in range(2, 250000, 4)]
%timeit res1 = sorted(list1 + list2)
%timeit res2 = list1 + list2; res2.sort()

6.73 ms ± 64.9 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
4.43 ms ± 38.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

[ProSev]

Метод sort() в данных условиях работает быстрее функции sorted(). На заметку.