Сортировка

Сортировка — расположение элементов последовательности в порядке возрастания или убывания по некоторому ключу. Это одна из самых изученных задач информатики: отсортированные данные позволяют искать двоичным поиском за O(log n), находить дубликаты и медиану, объединять наборы, строить индексы баз данных. На примере сортировки традиционно объясняют оценку сложности, рекурсию и принцип «разделяй и властвуй».

Свойства алгоритмов

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

Основные алгоритмы

Сортировка вставками берёт элементы по одному и вставляет на место в уже отсортированной части. Квадратичная в общем случае, но очень быстрая на маленьких и почти упорядоченных массивах — поэтому используется внутри гибридных алгоритмов.

Сортировка слиянием делит массив пополам, рекурсивно сортирует половины и сливает их за линейное время. Гарантирует O(n log n) и устойчивость, хорошо подходит для связных списков и внешней сортировки файлов, не помещающихся в память.

Быстрая сортировка (Тони Хоар, 1959) выбирает опорный элемент, разбивает массив на «меньше» и «больше» и рекурсивно сортирует части. На практике обычно самая быстрая из сравнительных благодаря работе на месте и хорошей локальности кэша, но при неудачном выборе опорного элемента деградирует до O(n²).

Пирамидальная сортировка строит двоичную кучу (см. Дерево и граф) и извлекает максимум n раз. O(n log n) в худшем случае без дополнительной памяти, но медленнее quicksort из-за неудобного доступа к памяти.

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:      # <= сохраняет устойчивость
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]

Нижняя граница

Любой алгоритм, который упорядочивает элементы только сравнениями, в худшем случае требует Ω(n log n) сравнений: существует n! перестановок, а каждое сравнение даёт лишь один бит информации, значит нужно не меньше log₂(n!) ≈ n log₂ n сравнений.^[1] Обойти границу можно, только используя структуру ключей: сортировка подсчётом для небольших целых, поразрядная для чисел и строк фиксированной длины.

Сортировка в стандартных библиотеках

На практике почти никогда не нужно писать сортировку самому — библиотечные реализации тщательно оптимизированы:

• Timsort (Тим Петерс, 2002) — гибрид слияния и вставок: находит уже упорядоченные участки («пробеги») и сливает их. Устойчив и очень быстр на реальных данных, которые часто частично упорядочены. Использовался в Python, Java (для объектов), Android; в Python 3.11 стратегия слияния заменена на более оптимальную Powersort.^[3]
• pdqsort (pattern-defeating quicksort) — быстрая сортировка с защитой от худшего случая: при неудачных разбиениях переключается на пирамидальную, на маленьких отрезках — на вставки. Используется в Go (slices.Sort) и в Rust (sort_unstable).^[4][5]
• Introsort — похожий гибрид quicksort, heapsort и вставок в std::sort C++.

users.sort(key=lambda u: (u.dept, -u.salary))      # Python: устойчиво, по ключу
sorted(words, key=str.casefold)                    # без учёта регистра

slices.SortFunc(users, func(a, b User) int { return cmp.Compare(a.Age, b.Age) })
slices.SortStableFunc(users, ...)                  // устойчивая версия

В Rust sort — устойчивая (на основе слияния, driftsort), sort_unstable — неустойчивая, но быстрее и без выделения памяти.^[6] Python предоставляет только устойчивую сортировку.^[2]

Практические советы

• Сортируйте по ключу (key=), а не через функцию сравнения — это быстрее: ключ вычисляется один раз на элемент.
• Строки на естественном языке сравнивают с учётом локали (collation): побайтовое сравнение UTF-8 ставит «Ё» после «я».
• Если нужны только k наибольших элементов, используйте кучу (heapq.nlargest) или частичную сортировку — O(n log k) вместо O(n log n).
• Для данных, не помещающихся в память, применяют внешнюю сортировку слиянием — так работают sort в Unix и ORDER BY в базах данных при нехватке памяти.

См. также

• Алгоритм и O-нотация
• Рекурсия
• Структуры данных
• Дерево и граф

Источники

1. Knuth — The Art of Computer Programming, Vol. 3: Sorting and Searching
2. Python Docs — Sorting Techniques
3. Tim Peters — listsort.txt (описание Timsort)
4. Orson Peters — Pattern-defeating Quicksort (2021)
5. Go — package sort / slices
6. Rust — slice::sort_unstable