Strand Sort

Проблема

Сортировка слиянием эффективно объединяет уже отсортированные части, но сначала слепо делит массив пополам, не глядя на то, что в данных уже может быть естественный порядок. Если во входных данных уже встречаются длинные возрастающие участки (частично отсортированные данные, объединение нескольких предварительно отсортированных источников), хочется алгоритма, который распознаёт и использует эти участки напрямую, а не проходит через ненужное деление.

Решение

Из оставшихся (ещё не обработанных) элементов извлекается «прядь»: первый элемент берётся всегда, а следующие добавляются к пряди, только если они не меньше последнего элемента пряди - так формируется самая длинная возрастающая подпоследовательность, встречающаяся по порядку в оставшихся данных. Все элементы, не попавшие в прядь, остаются для следующей итерации. Готовая прядь сливается (как в сортировке слиянием) с уже накопленным результатом. Процесс повторяется, пока не останется необработанных элементов.

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

Проследим сортировку прядями на массиве [6, 2, 5, 1, 9, 3, 8, 4, 7] (n = 9). Первая прядь: 6, затем 9 (первый элемент, не меньший 6) - [6, 9], длина 2. Оставшиеся [2, 5, 1, 3, 8, 4, 7] дают вторую прядь [2, 5, 8], длина 3. Оставшиеся [1, 3, 4, 7] образуют третью прядь целиком - [1, 3, 4, 7], длина 4. Три итерации, длины прядей растут - 2, 3, 4 - и покрывают все 9 элементов.

Слияние этих трёх прядей стоит 0 + 4 + 7 = 11 сравнений: первое слияние (пустой результат с прядью длины 2) не требует сравнений вовсе, второе слияет 2 и 3 элемента за 4 сравнения, третье - 5 и 4 элемента за 7. Итого на n = 9 массив отсортирован за 3 извлечения прядей вместо, например, n − 1 = 8 сравнений одной сортировкой вставками с худшим случаем - здесь длинные пряди резко сокращают число итераций.

Худший случай - обратно отсортированный массив [9, 8, 7, 6, 5, 4, 3, 2, 1]: каждая прядь состоит ровно из одного элемента (следующий элемент всегда меньше предыдущего), и требуется 9 итераций для массива из 9 элементов. Это вырождает алгоритм в поведение, эквивалентное сортировке вставками - O(n²).

Лучший случай - уже отсортированный массив [1, 2, ..., 9]: первая же прядь захватывает все 9 элементов за 1 итерацию, и единственное слияние - с пустым результатом - обходится без единого сравнения. Отсюда и заявленная O(n) в лучшем случае: один проход по массиву, ни одной операции слияния сверх копирования.

В отличие от классической сортировки слиянием, чья рекуррентность T(n) = 2T(n/2) + O(n) не зависит от содержимого массива, сортировка прядями адаптивна: число итераций и их размер полностью определяются тем, сколько и каких по длине возрастающих участков реально есть во входных данных. Это плата и выигрыш одновременно - предсказуемости меньше, но на подходящих данных алгоритм заметно быстрее.

Классический раздел «естественного слияния» (natural merging) в третьем томе Дональда Кнута «The Art of Computer Programming» описывает семейство алгоритмов, которые вместо произвольного деления массива объединяют уже существующие в данных возрастающие участки (runs) - сортировка прядями формализует именно эту идею, выбирая на каждом шаге ровно одну самую длинную такую последовательность.

Современный наследник этой идеи - Timsort: вместо того чтобы искать сколь угодно длинную прядь ценой одного линейного прохода за раз, он находит естественные возрастающие (и убывающие) участки, при необходимости растягивает короткие до порогового minrun, и сливает их «умным» слиянием с режимом галопирования. Сортировка прядями - концептуальный, максимально прямолинейный предок этой оптимизации.

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

Связные списки с уже частично упорядоченными данными - объединение нескольких предварительно отсортированных потоков (логов, очередей) без промежуточного преобразования в массив.

Как учебный контраст с классической сортировкой слиянием - обе рекурсивно или итеративно опираются на слияние отсортированных частей, но merge sort делит массив вслепую, а сортировка прядями находит существующий порядок.

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

Как введение к идее Timsort - прежде чем изучать minrun, галопирование и стек слияний Timsort, сортировка прядями показывает базовую идею «искать существующий порядок» в её самом простом виде.

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

Donald Knuth, «The Art of Computer Programming, Volume 3: Sorting and Searching» (раздел 5.2.4, «natural merging») - классическое описание семейства алгоритмов, использующих естественные возрастающие участки данных вместо произвольного деления.

Timsort (стандартная сортировка CPython list.sort() и Java Arrays.sort() для объектов) явно находит возрастающие и убывающие участки во входных данных - та же базовая идея, что и у сортировки прядями, но с порогом minrun и оптимизированным слиянием вместо чисто жадного извлечения.

Слияние отсортированных лог-файлов и очередей событий в системах обработки данных - когда несколько источников уже упорядочены по времени, стратегия «вытянуть длинную цепочку и слить» напрямую применима без модификации.

Реализации сортировки для связных списков в учебных курсах по структурам данных часто используют идею прядей как более простую альтернативу merge sort на списках, поскольку не требует вычисления середины списка для деления пополам.

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

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

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

• Слияние нескольких предварительно отсортированных журналов или очередей событий - если каждый источник уже упорядочен, стратегия «вытянуть длинную возрастающую цепочку и слить» эффективно объединяет их.
• Реализации сортировки для связных списков нередко используют идею прядей, поскольку извлечение подпоследовательности через перестановку указателей естественно для списков и избегает накладных расходов на произвольный доступ по индексу.