Как называется дефолтная сортировка в Python?

Дефолтная сортировка в Python — это алгоритм Timsort (Tim Peters, 2002). Это гибридный алгоритм, который сочетает преимущества merge sort и insertion sort. Давайте разберёмся в его особенностях и применении.

Что такое Timsort

Timsort — это адаптивный гибридный алгоритм сортировки, который автоматически выбирает оптимальную стратегию в зависимости от характера данных:

# Базовое использование (использует Timsort)
data = [3, 1, 4, 1, 5, 9, 2, 6, 5]
data.sort()  # Сортирует in-place
print(data)  # [1, 1, 2, 3, 4, 5, 5, 6, 9]

# Возвращает новый отсортированный список
sorted_data = sorted(data)

Характеристики Timsort

Стабильность

Timsort сохраняет относительный порядок равных элементов:

students = [("Alice", 90), ("Bob", 85), ("Charlie", 90)]
sorted_by_grade = sorted(students, key=lambda x: x[1])
print(sorted_by_grade)
# [("Bob", 85), ("Alice", 90), ("Charlie", 90)] — порядок Alice и Charlie сохранён

Сложность

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

Это делает Timsort эффективным даже для слегка отсортированных данных:

import time

# Лучший случай — уже отсортированные данные
data_sorted = list(range(1000000))
start = time.time()
data_sorted.sort()
print(f"Отсортированные данные: {time.time() - start:.4f} сек")

# Худший случай — обратный порядок
data_reverse = list(range(1000000, 0, -1))
start = time.time()
data_reverse.sort()
print(f"Обратный порядок: {time.time() - start:.4f} сек")

Как работает Timsort

Алгоритм состоит из нескольких фаз:

1. Разбиение на "runs"

Данные разбиваются на маленькие куски (runs), которые сортируются insertion sort:

# Минимальный размер run зависит от размера данных
# Обычно это степень 2: 32, 64, 128 и т.д.

data = [64, 34, 25, 12, 22, 11, 90, 88, 45, 50, 30, 28, 20, 15]
# Разбивается на маленькие куски и сортируется каждый

2. Слияние runs (merge)

Отсортированные куски объединяются в один список:

# Пример логики слияния двух списков
def merge_sorted_lists(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

left = [1, 3, 5]
right = [2, 4, 6]
print(merge_sorted_lists(left, right))  # [1, 2, 3, 4, 5, 6]

Сравнение параметров сортировки

# Сортировка с ключевой функцией
words = ["python", "django", "flask", "fastapi"]

# По длине слова
print(sorted(words, key=len))  # ['flask', 'python', 'django', 'fastapi']

# По алфавиту (по умолчанию)
print(sorted(words))  # ['django', 'fastapi', 'flask', 'python']

# В обратном порядке
print(sorted(words, reverse=True))  # ['python', 'flask', 'fastapi', 'django']

Практические примеры

Сортировка DataFrame в pandas

пандас тоже использует Timsort под капотом:

import pandas as pd

df = pd.DataFrame({
    "name": ["Alice", "Bob", "Charlie"],
    "age": [25, 30, 25],
    "salary": [50000, 60000, 55000]
})

# Сортировка по одной колонке
df_sorted = df.sort_values("age")

# Сортировка по нескольким колонкам
df_sorted = df.sort_values(["age", "salary"])

Сортировка сложных структур данных

# Сортировка списка словарей
employees = [
    {"name": "Alice", "department": "Data", "salary": 80000},
    {"name": "Bob", "department": "Engineering", "salary": 90000},
    {"name": "Charlie", "department": "Data", "salary": 75000}
]

# По зарплате
sorted_by_salary = sorted(employees, key=lambda x: x["salary"], reverse=True)

# По названию отдела, потом по имени
sorted_employees = sorted(employees, key=lambda x: (x["department"], x["name"]))

Когда Timsort особенно эффективен

1. Частично отсортированные данные — O(n) вместо O(n log n)
2. Маленькие массивы — insertion sort на run'ах очень быстр
3. Стабильная сортировка важна — сохраняет порядок равных элементов
4. Реальные данные — часто имеют естественные паттерны

Альтернативы и когда их использовать

# NumPy имеет собственные алгоритмы (быстрее для массивов)
import numpy as np

array = np.array([3, 1, 4, 1, 5, 9])
sorted_array = np.sort(array)  # Использует quicksort или heapsort

# Сортировка по индексам (argsort)
indices = np.argsort(array)
print(indices)  # [1, 3, 0, 2, 4, 5]

Итоговые выводы

• Timsort — универсальный, стабильный и эффективный алгоритм
• Работает O(n log n) в худшем случае, но O(n) на отсортированных данных
• Стабилен: сохраняет порядок равных элементов
• Оптимизирован для реальных данных, а не для худших случаев
• Используется в Python, Java, Android и других платформах

Для Data Scientist'а важно понимать, что сортировка в Python уже оптимизирована, и в 99% случаев вам не нужно писать свой алгоритм сортировки.