Встроенный метод sort() и функция sorted() в Python используют Timsort — гибридный алгоритм сортировки, разработанный специально для Python в 2002 году.
Timsort объединяет два классических алгоритма:
Он работает, обнаруживая естественно упорядоченные подпоследовательности в данных — так называемые runs — и грамотно их объединяя.
O(n log n) в худшем и среднем случаеO(n) когда данные уже отсортированы или почти отсортированыO(n) вспомогательной памятиnumbers = [3, 1, 4, 1, 5, 9]
numbers.sort() # сортирует на месте
sorted_copy = sorted(numbers) # возвращает новый список
Timsort считается одним из наиболее эффективных универсальных алгоритмов сортировки для реальных данных, поскольку данные на практике часто частично упорядочены. Его устойчивость также делает его надёжным выбором при последовательной сортировке объектов по нескольким атрибутам.
Timsort достигает временной сложности O(n) в лучшем случае, когда входные данные уже отсортированы или почти отсортированы, потому что может идентифицировать и использовать существующие runs без активного слияния.
Новый — ещё не проверен сообществом
Вы