Какой алгоритм сортировки используется в стандартных функциях Python?

В Python для сортировки списков и других итерируемых объектов (методы list.sort() и встроенная функция sorted()) используется алгоритм Timsort.

Что такое Timsort? Это гибридный алгоритм сортировки, разработанный Тимом Питерсом в 2002 году. Он сочетает в себе лучшие черты:

• Сортировки слиянием (Merge Sort): Эффективна для больших наборов данных.
• Сортировки вставками (Insertion Sort): Эффективна для небольших наборов данных и частично отсортированных данных.

Почему Timsort? Timsort оптимизирован для работы с реальными данными, которые часто содержат уже отсортированные или частично отсортированные подпоследовательности (так называемые "runs"). Он эффективно использует эти "runs" для ускорения процесса сортировки.

Ключевые особенности:

• Стабильность: Сохраняет относительный порядок элементов с одинаковыми значениями. Это важно, например, при сортировке по нескольким критериям.
• Временная сложность:
  • Лучший случай: O(n) – если данные уже отсортированы.
  • Средний и худший случаи: O(n log n) – для большинства сценариев.
• Пространственная сложность: O(n) в худшем случае, но может быть O(log n) в лучшем, так как использует дополнительную память для временных массивов.

Пример использования:

data = [5, 2, 9, 1, 5, 6, 3]

# Использование встроенной функции sorted() - возвращает новый отсортированный список
sorted_data = sorted(data)
print(f"sorted(): {sorted_data}") # Вывод: [1, 2, 3, 5, 5, 6, 9]

# Использование метода list.sort() - сортирует список на месте (in-place)
data.sort()
print(f"list.sort(): {data}")    # Вывод: [1, 2, 3, 5, 5, 6, 9]