Merciful Stalin Sort (сортировка «Милосердный Сталин») — это новый алгоритм сортировки, вдохновлённый пресловутым Stalin Sort (сталинской сортировкой). В ходе развлекательного эксперимента со сталинской сортировкой возникла интригующая идея: что, если вместо удаления выбивающихся элементов, сохранить те, которые идут по порядку, и рекурсивно упорядочить остальные? Логика заключалась в том, чтобы добиться повышения производительности за счёт уменьшения массива, требующего сортировки, особенно в случае частично упорядоченных массивов. Это и привело к разработке сортировки «Милосердный Сталин».

▍ Разработка и концепция

Оригинальная сталинская сортировка работает путём прохождения по массиву и удаления любого элемента, находящегося не на своём месте, по сути «производя зачистку» для получения упорядоченного массива оставшихся элементов. Такой радикальный подход, хоть и забавен, но для большинства практических случаев не подходит.

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

Для решения этой проблемы алгоритм был дополнен обратным проходом. После того, как прямой проход собирает элементы в возрастающем порядке, обратный проход повторно пробегается по оставшимся элементам, собирая расположенные в порядке убывания. Это добавление значительно повысило скорость обратной сортировки массивов за счёт сокращения глубины рекурсии и обработки как возрастающей, так и убывающей последовательностей.

▍ Обзор алгоритма

Сортировка «Милосердный Сталин» осуществляется в три основных этапа:

1. Прямой проход: перебираем массив с начала, оставляя элементы, расположенные в порядке возрастания. Выпадающие элементы при этом собираются в отдельный массив.
2. Обратный проход: перебираем неупорядоченные элементы с конца, сохраняя те, которые идут в порядке убывания. Остающиеся элементы собираются в другой массив.
3. Слияние и рекурсивная сортировка: объединяем отсортированные элементы, полученные прямым и обратным проходом. Если при этом остались неотсортированные, рекурсивно применяем к ним милосердную сортировку и соединяем результат с ранее объединённым массивом.

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

Анализ временно́й сложности

▍ Лучший сценарий: O(n)

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

▍ Усреднённый и худший сценарии: O(n log n)

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

При каждом рекурсивном вызове массив делится на три части:

• Элементы, упорядоченные по возрастанию: собранные во время прямого прохода.
• Элементы, упорядоченные по убыванию: собранные во время обратного прохода.
• Оставшиеся неупорядоченные элементы: которые не были собраны в прошлых проходах.

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

На каждом уровне рекурсии алгоритм выполняет O(n) работы:

• Каждый проход вперёд и назад занимает O(n) времени.
• Объединение отсортированных массивов также занимает O(n) времени.

Следовательно, общая временна́я сложность составляет O(n log n), поскольку на каждом из O(log n) уровней рекурсии выполняется O(n) работы.

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

▍ Эмпирический анализ

Путём комплексного тестирования скорость выполнения милосердной сортировки была сопоставлена со скоростью традиционных алгоритмов, а именно сортировки слиянием, быстрой сортировки, пузырьковой сортировки и сортировки вставками.

В тестах использовались массивы, имеющие различное количество и изначальный порядок элементов: случайные массивы, упорядоченные, массивы с обратным порядком, а также частично упорядоченные массивы с 10%, 30% и 50% неотсортированных элементов.
Подробные результаты тестирования лежат в results.txt.

▍ Массивы со случайным порядком элементов

На массивах со случайным порядком элементов милосердная сталинская сортировка уступает сортировке слиянием и быстрой сортировке. Издержки, связанные с прямым и обратным проходом, в сочетании с рекурсивными вызовами снижают её эффективность в отношении неупорядоченных данных. График показывает, что с увеличением размера массива время выполнения милосердной сортировки растёт стремительнее, чем сортировки слиянием и быстрой сортировки. Но при этом она превосходит пузырьковую сортировку и сортировку вставками, в особенности на более объёмных массивах.

▍ Упорядоченные массивы

На упорядоченных массивах алгоритм работает продуктивно по сравнению с сортировкой вставками. Прямой проход собирает все элементы, и рекурсивные вызовы не требуются, что приводит к линейной временно́й сложности. На графике отражено минимальное время выполнения, растущее линейно с увеличением размера массива, что демонстрирует эффективность алгоритма в этом сценарии.

▍ Массивы с обратным порядком

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

Примечание: без обратного прохода этот сценарий был наихудшим для милосердной сортировки, которая уступала даже пузырьковой и сортировке вставками.

▍ Частично упорядоченные массивы

10% элементов неупорядоченно


30% элементов неупорядоченно


50% элементов неупорядоченно

Чем выше степень упорядоченности, тем более высокую производительность показывает алгоритм. Его работа упрощается за счёт того, что начальные проходы собирают более крупные упорядоченные последовательности, тем самым уменьшая размер массивов, требующих последующей рекурсивной сортировки. Похоже, чем меньше неотсортированных элементов в массиве, тем эффективнее с ним справляется милосердный Сталин. В отношении массива, содержащего всего 10% неупорядоченных элементов, он даже начинает конкурировать с сортировкой слиянием. Однако по мере уменьшения упорядоченности этот алгоритм начинает отставать от той же сортировки слиянием и быстрой сортировки, которые менее чувствительны к степени изначальной хаотичности элементов.

▍ Производительность сортировки «Милосердный Сталин»

График показывает время выполнения милосердной сортировки в отношении различных типов и размеров массивов. Для наглядности в нём используются логарифмические шкалы

Практические результаты показывают, что вопреки некоторому выигрышу в случае изначальной упорядоченности элементов, при обработке масштабных или случайно упорядоченных наборов данных эффективность «Милосердного Сталина» несопоставима с такими алгоритмами, как сортировка слиянием и быстрая сортировка. По мере увеличения размера массива издержки ресурсов, затрачиваемые на множественные проходы и рекурсивные вызовы, становятся всё более существенными. Более того, для каждого рекурсивного вызова алгоритм не может обработать достаточное количество элементов, чтобы добиться ощутимого прироста производительности.

В сравнении с пузырьковой сортировкой и сортировкой вставкой «Милосердный Сталин» лучше справляется с большими массивами, особенно, когда они уже частично упорядочены. В среднем это подчёркивает его относительное превосходство перед остальными рассматриваемыми алгоритмами.

Возможные оптимизации

▍ Выполнение прохода на основе эвристики

Добавить эвристику для определения, какие проходы нужно выполнять — прямой, обратный или же оба — путём анализа упорядоченности массива или вычисления его «балла упорядоченности» на основе сопоставления соседних элементов. Например, подсчёт количества возрастающих пар в сравнении с убывающими поможет выбрать оптимальное направление прохода, сократив ненужные вычисления и оптимизировав производительность в отношении массивов с отчётливыми трендами упорядоченности.

▍ Адаптивная стартовая точка

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

▍ Заключение

Алгоритм «Милосердный Сталин» воплощает интересную концепцию, стремясь оптимизировать процесс сортировки за счёт избирательного сохранения элементов и рекурсии. Однако эмпирическое тестирование показывает, что в большинстве популярных случаев использования он не превосходит традиционные алгоритмы сортировки. «Милосердный Сталин» превосходно справляется, когда массив уже упорядочен, частично упорядочен или упорядочен наоборот, но испытывает трудности с данными в случайном порядке.

Telegram-канал со скидками, розыгрышами призов и новостями IT ?