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

Асимптотическая сложность сортировки в Python

Дефолтная сортировка в Python использует алгоритм Timsort, который был разработан Тимом Петерсом и внедрён в Python 2.3. Это гибридный алгоритм, сочетающий преимущества merge sort и insertion sort.

Асимптотические сложности Timsort

• Лучший случай: O(n) - когда данные уже отсортированы
• Средний случай: O(n log n) - типичная ситуация
• Худший случай: O(n log n) - гарантирует логарифмическую сложность всегда
• Пространственная сложность: O(n) - требуется дополнительная память

Структура Timsort

1. Разделение на small runs - массив разбивается на подмассивы (64 элемента)
2. Insertion sort - каждый подмассив сортируется insertion sort
3. Merge - подмассивы объединяются merge sort алгоритмом

Это сочетание позволяет:

• Insertion sort эффективен на малых данных
• Merge sort гарантирует логарифмическую сложность
• Адаптивность к уже отсортированным данным

Практический код

import time
import random

def measure_sort_time(n):
    data = [random.randint(1, 1000000) for _ in range(n)]
    start = time.time()
    sorted_data = sorted(data)
    end = time.time()
    return end - start

for n in [1000, 10000, 100000]:
    t = measure_sort_time(n)
    print(f'n={n}: {t:.6f}s')

Преимущества Timsort

• Быстрый на реальных данных - использует частично отсортированные последовательности
• Стабильный - сохраняет порядок равных элементов
• Адаптивный - замечает существующий порядок
• Предсказуемый - O(n log n) даже в худшем случае

Альтернативы

• Java: Dual-Pivot Quicksort
• C++: introsort
• JavaScript: V8 использует Timsort

Timsort - один из лучших алгоритмов благодаря отличной практической производительности.