Patience Sort

Проблема

Многие алгоритмы сортировки сравнением требуют либо явного разбиения (quicksort), либо явного слияния заранее упорядоченных половин (merge sort). Хочется алгоритма, который бы строил упорядоченные группы «на лету», раскладывая элементы по ходу единственного прохода, а не заранее зная, как делить массив.

Решение

Элементы по очереди «раскладываются» на стопки: каждая карта кладётся на первую слева стопку, чей верх больше или равен ей (поиск такой стопки - бинарный, O(log n)); если подходящей стопки нет, начинается новая стопка. В результате получается несколько стопок, каждая из которых по построению убывает сверху вниз. Финальный шаг - слить эти стопки, как k отсортированных списков, многократно забирая минимальный верхний элемент среди всех стопок (эффективно - через кучу).

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

Проследим раскладку на конкретном массиве [6, 3, 5, 1, 8, 2, 7, 4] (n = 8). Карта 6 открывает стопку 1. Карта 3 находит подходящую стопку 1 (верх 6 ≥ 3) и ложится на неё. Карта 5 не подходит ни одной стопке (верх стопки 1 теперь 3 < 5) - открывается стопка 2. После всех восьми карт получаются три стопки: [6,3,1], [5,2], [8,7,4] с верхними элементами 1, 2, 4. Три стопки - и действительно, длиннейшая возрастающая подпоследовательность входа (например, 3, 5, 8 или 1, 2, 7) имеет длину ровно 3.

Раскладка стоит O(n log n): для каждой из n карт бинарный поиск идёт по массиву стопок длиной до k (текущее число стопок, k ≤ n), то есть O(log k) на карту. В худшем случае, когда вход отсортирован по убыванию, каждая новая карта меньше верха любой стопки - подходящей не находится, и открывается новая стопка на каждом шаге: итог - n стопок по одному элементу.

Слияние стопок реализовано через min-heap индексов стопок, а не наивным линейным перебором всех стопок на каждый выходной элемент. Разница принципиальна: линейный перебор стоил бы O(k) на элемент вывода, то есть O(n·k) суммарно - при n стопках (худший случай раскладки, вход по убыванию) это выродилось бы в O(n²). Куча же даёт O(log k) на извлечение и восстановление порядка, то есть честные O(n log n) при любом числе стопок.

На примере из первого абзаца слияние 8 элементов из 3 стопок через кучу делает всего 4 реальных обмена внутри siftDown (по одному при выводе каждого из первых четырёх элементов, пока в куче остаются 2-3 стопки) - остальные 4 извлечения не требуют перестановок, поскольку куча к этому моменту уже мала (1-2 стопки). Построение самой кучи перед слиянием не делает ни одного обмена: верхние элементы стопок 1, 2, 4 уже отсортированы по возрастанию силой самого инварианта бинарного поиска, поэтому массив индексов [0, 1, 2] - готовая min-heap без какой-либо предобработки.

Эта пара наблюдений - что построение кучи почти всегда бесплатно, а слияние ограничено O(n log n) даже в худшем случае - и даёт итоговую гарантию алгоритма: раскладка O(n log n) плюс слияние O(n log n) равно O(n log n) суммарно, без скрытого квадратичного члена, который был бы у наивного линейного слияния.

Связь числа стопок с длиной LIS - не совпадение, а прямое следствие теоремы Дилворта (Dilworth, 1950): в любом частичном порядке минимальное число цепей, покрывающих все элементы, равно максимальному размеру антицепи. Здесь «цепь» - убывающая сверху вниз стопка (образует возрастающую подпоследовательность при чтении снизу вверх), а «антицепь» - множество элементов, никакие два из которых не сравнимы в порядке «меньше и левее» - то есть возрастающая подпоследовательность. Число стопок при жадной раскладке (класть карту на первую подходящую) минимально по построению, поэтому оно и равно длине LIS.

Карточный пасьянс, давший алгоритму имя («patience» - британский синоним слова «solitaire»), был математически проанализирован К. Л. Мэллоуcом (C. L. Mallows) в статье 1962 года о статистике числа стопок при случайной раскладке карт. Алгоритмический вариант с бинарным поиском для нахождения LIS за O(n log n) и его связь со случайными перестановками подробно разобраны в статье Дэвида Олдоса и Перси Дьяконписа (David Aldous, Persi Diaconis), «Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem» (Bulletin of the AMS, 1999).

Итог: пасьянсная сортировка платит O(n) памяти под стопки и неустойчивость слияния за две вещи одновременно - гарантированное O(n log n), не зависящее от структуры входа, и попутный ответ на задачу LIS без отдельного прохода. На практике это делает её скорее учебным и специализированным инструментом (там, где LIS реально нужна), чем заменой merge sort или Timsort для повседневной сортировки.

Нюансы выбора

Нужны и сортировка, и LIS одновременно - вместо отдельного O(n log n) алгоритма для LIS и отдельной сортировки, раскладка по стопкам сразу даёт оба ответа: отсортированный массив после слияния и длину LIS как число стопок.

Против merge sort - если LIS не нужна, обычный merge sort почти всегда предпочтительнее: он устойчив, не требует бинарного поиска и кучи для слияния, и его константы на практике ниже.

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

В учебных курсах по комбинаторике и анализу алгоритмов - раскладка по стопкам одновременно иллюстрирует жадные стратегии, теорему Дилворта и связь сортировки с задачами на подпоследовательности, что делает её удобным мостом между темами.

Примеры в коде

C. L. Mallows, «Problem 62-2, Patience Sorting» (SIAM Review, 1962) - первый математический анализ карточной игры пасьянс «patience», включая статистику ожидаемого числа стопок при случайной раскладке колоды.

David Aldous, Persi Diaconis, «Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem» (Bulletin of the AMS, 1999) - связывает раскладку по стопкам с глубокой теорией случайных перестановок и распределением Трейси-Уидома (Tracy-Widom) из теории случайных матриц.

Соответствие Робинсона-Шенстеда (Robinson-Schensted correspondence) в алгебраической комбинаторике строит из перестановки пару таблиц Юнга через вставку по строкам; столбцы получившейся таблицы соответствуют в точности стопкам пасьянсной раскладки того же входа.

Название «patience» - британский английский термин для того, что в США называют «solitaire»: класс карточных игр для одного игрока, где карты раскладываются по определённым правилам - именно эта раскладка легла в основу названия алгоритма.

Когда применять

• Когда наряду с сортировкой нужна длиннейшая возрастающая подпоследовательность - пасьянсная сортировка решает обе задачи по сути одним алгоритмом.
• Как наглядная демонстрация связи между карточными играми, жадными стратегиями и гарантией O(n log n) - популярна в учебных курсах по анализу алгоритмов.

Примеры из практики

• Утилита `git blame`/поиск наименьшего diff в системах контроля версий использует вариант LIS, вычислимый через раскладывание по стопкам, для нахождения минимального набора изменений между версиями файла.
• Задачи на анализ последовательностей (биоинформатика, финансовые временные ряды), где нужен эффективный поиск наибольшей возрастающей подпоследовательности значений.