Конспект: слиянием и быстрая

Понятия

Сортировка слиянием - делит массив пополам (по позиции), рекурсивно сортирует половины и СЛИВАЕТ их за Θ(n). T(n) = 2T(n/2) + n = Θ(n·log n) В ЛЮБОМ случае. Устойчива, требует Θ(n) дополнительной памяти.

Слияние - два указателя в началах отсортированных частей; сравнивают головы, меньшую берут в результат, двигают её указатель; в конце дописывают хвост. Каждый элемент раз - Θ(n).

Быстрая сортировка - выбирает опорный, РАЗБИВАЕТ массив на «меньше» и «больше» него (по значению), рекурсивно сортирует части. В среднем Θ(n·log n), на месте (Θ(log n) под стек), не устойчива.

Разбиение Хоара - два указателя навстречу: левый ищет ≥ опорного, правый ≤ опорного, найденную пару меняют, пока не встретятся. На месте, Θ(n).

Худший случай быстрой - Θ(n²), когда опорный делит по одному элементу (T(n)=T(n−1)+n); дерево вырождается в цепочку длины n.

Что унести

Два n·log n-алгоритма с разными компромиссами:

Слияние - «гарантия и устойчивость ценой памяти»; быстрая - «память и скорость на практике ценой худшего случая». Обе делят задачу пополам (log n уровней) и тратят Θ(n) на уровень; разница - в том, ЧТО делят: слияние по позиции (и потом дорого сливает), быстрая по значению опорного (и не сливает вовсе).

Худший случай быстрой - Θ(n²) при плохом опорном; опорный-первый ломается на уже ОТСОРТИРОВАННОМ входе (первый = минимум, деление 0:(n−1)). Лечат: - случайный опорный - плохой вход маловероятен; - медиана трёх - чинит отсортированный вход; - переключение на пирамидальную при глубокой рекурсии (introsort) - гарантия n·log n.

Разбиение - самостоятельный приём: тот же шаг лежит в основе быстрого выбора k-го элемента (quickselect, раздел про порядковые статистики).

Ловушки джокера

Забыл, что слияние ест Θ(n) памяти. Это её природа, а не баг; на жёсткой экономии памяти - против неё.

Сломал базу рекурсии (len <= 1). Рекурсия не завершится.

При слиянии равных берёшь из правой части (< вместо <= с приоритетом левой). Молча теряешь устойчивость.

Опорный-первый в проде. Отлично на случайных тестах, Θ(n²) и переполнение стека на отсортированном/почти отсортированном реальном входе.

Думаешь, что случайный опорный делает Θ(n²) невозможным. Он делает его лишь маловероятным; строгую гарантию даёт переключение на пирамидальную или слияние.

Проверь себя

Почему сортировка слиянием - n·log n в любом случае?

Как слить две отсортированные части за Θ(n) и почему это устойчиво?

Как работает разбиение Хоара и почему быстрая сортировка - на месте?

Откуда у быстрой сортировки берётся Θ(n²) и почему опорный-первый плох на отсортированном входе?

Чем слияние и быстрая отличаются по памяти и устойчивости - и что когда выбрать?