# Сортировка

> Упорядочивание элементов по ключу; основные алгоритмы — быстрая, слиянием, пирамидальная, вставками — и гибриды Timsort и pdqsort, используемые в стандартных библиотеках.

Источник: https://llmdocs.ru/wiki/sorting/ · обновлено 2026-11-09 · лицензия CC BY-SA 4.0

- **Нижняя граница сравнений**: Ω(n log n)
- **Быстрые алгоритмы**: quicksort, mergesort, heapsort — O(n log n)
- **Простые алгоритмы**: вставками, выбором, пузырьком — O(n²)
- **Без сравнений**: подсчётом, поразрядная — O(n + k)
- **Python, Java (объекты)**: Timsort / Powersort
- **Go, Rust (unstable)**: pdqsort
**Сортировка** — расположение элементов последовательности в порядке возрастания или убывания по некоторому ключу. Это одна из самых изученных задач информатики: отсортированные данные позволяют искать двоичным поиском за O(log n), находить дубликаты и медиану, объединять наборы, строить [индексы](https://llmdocs.ru/wiki/database-index.md) баз данных. На примере сортировки традиционно объясняют [оценку сложности](https://llmdocs.ru/wiki/big-o.md), рекурсию и принцип «разделяй и властвуй».

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

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

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

| Алгоритм | Среднее | Худшее | Память | Устойчив |
|---|---|---|---|---|
| Вставками (insertion) | O(n²) | O(n²) | O(1) | да |
| Выбором (selection) | O(n²) | O(n²) | O(1) | нет |
| Пузырьком (bubble) | O(n²) | O(n²) | O(1) | да |
| Слиянием (merge) | O(n log n) | O(n log n) | O(n) | да |
| Быстрая (quick) | O(n log n) | O(n²) | O(log n) | нет |
| Пирамидальная (heap) | O(n log n) | O(n log n) | O(1) | нет |
| Подсчётом (counting) | O(n + k) | O(n + k) | O(k) | да |
| Поразрядная (radix) | O(d·(n + k)) | O(d·(n + k)) | O(n + k) | да |

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

**Сортировка слиянием** делит массив пополам, [рекурсивно](https://llmdocs.ru/wiki/recursion.md) сортирует половины и сливает их за линейное время. Гарантирует O(n log n) и устойчивость, хорошо подходит для связных списков и внешней сортировки файлов, не помещающихся в память.

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

**Пирамидальная сортировка** строит двоичную кучу (см. [Дерево и граф](https://llmdocs.ru/wiki/trees-graphs.md)) и извлекает максимум n раз. O(n log n) в худшем случае без дополнительной памяти, но медленнее quicksort из-за неудобного доступа к памяти.

```python
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++.

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

```go
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](https://llmdocs.ru/wiki/unicode-utf8.md) ставит «Ё» после «я».
- Если нужны только k наибольших элементов, используйте кучу (`heapq.nlargest`) или частичную сортировку — O(n log k) вместо O(n log n).
- Для данных, не помещающихся в память, применяют внешнюю сортировку слиянием — так работают `sort` в Unix и `ORDER BY` в базах данных при нехватке памяти.

## См. также

- [Алгоритм и O-нотация](https://llmdocs.ru/wiki/big-o.md)
- [Рекурсия](https://llmdocs.ru/wiki/recursion.md)
- [Структуры данных](https://llmdocs.ru/wiki/data-structures.md)
- [Дерево и граф](https://llmdocs.ru/wiki/trees-graphs.md)

## Источники

1. [Knuth — The Art of Computer Programming, Vol. 3: Sorting and Searching](https://www-cs-faculty.stanford.edu/~knuth/taocp.html)
2. [Python Docs — Sorting Techniques](https://docs.python.org/3/howto/sorting.html)
3. [Tim Peters — listsort.txt (описание Timsort)](https://github.com/python/cpython/blob/main/Objects/listsort.txt)
4. [Orson Peters — Pattern-defeating Quicksort (2021)](https://arxiv.org/abs/2106.05123)
5. [Go — package sort / slices](https://pkg.go.dev/slices#Sort)
6. [Rust — slice::sort_unstable](https://doc.rust-lang.org/std/primitive.slice.html#method.sort_unstable)