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

В Python встроенные методы сортировки (sorted() и list.sort()) используют алгоритм Timsort, который имеет:

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

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

import timeit

data = [5, 2, 3, 1, 4]
sorted_data = sorted(data)  # O(n log n) в среднем
print(sorted_data)  # [1, 2, 3, 4, 5]

Для сравнения:

• Пузырьковая сортировка: O(n²)
• Быстрая сортировка: O(n log n) в среднем, O(n²) в худшем
• Сортировка слиянием: O(n log n), но требует O(n) дополнительной памяти