Какой алгоритм сортировки используется при сортировке списков в Python?

Python (CPython) использует алгоритм Timsort для сортировки списка (метод .sort() и функция sorted()). Timsort – это гибридная сортировка, основанная на слиянии, оптимизированная под реальные данные: он эффективно обрабатывает уже частично отсортированные последовательности. У Timsort худшая сложность O(n log n), лучшая – O(n). Он стабильный (не меняет порядок равных элементов). Этот алгоритм был специально разработан для Python и Java, чтобы показывать хорошую производительность на разнообразных входных данных.