Какие знаешь сложности алгоритма сортировки Python

В Python встроенная функция sorted() и метод списка .sort() используют алгоритм Timsort — гибридный алгоритм, сочетающий сортировку вставками и слиянием.

Сложность:

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

Нюансы:

• Timsort адаптивен: эффективно обрабатывает частично упорядоченные данные.
• Стабилен: сохраняет порядок равных элементов.

Пример:

data = [5, 2, 9, 1, 5, 6]
sorted_data = sorted(data)  # O(n log n)
data.sort()                 # O(n log n), in-place

Для небольших списков (n < 1000) разница в скорости между алгоритмами может быть незначительной, но Timsort оптимален для реальных данных.