Какая асимптотическая сложность дефолтной сортировки в Python

В Python стандартная сортировка (sorted() или list.sort()) использует алгоритм Timsort. Его асимптотическая сложность:

• Лучший случай: O(n) — когда массив уже отсортирован.
• Средний и худший случай: O(n log n) — для произвольных данных.

Timsort — гибридный алгоритм (слияние + вставки), оптимизированный для реальных данных (частично упорядоченных массивов).

Пример:

data = [5, 2, 9, 1, 5]
sorted_data = sorted(data)  # O(n log n) в худшем случае