Library Sort

Проблема

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

Решение

Элементы хранятся в массиве вдвое большего размера (capacity), где часть ячеек пуста (null) - это и есть «зазоры», равномерно распределённые между заполненными элементами. Чтобы вставить новый элемент: бинарным поиском среди заполненных ячеек находится позиция, куда он должен встать по порядку; если целевая ячейка пуста - элемент просто кладётся туда; если занята - элементы сдвигаются по направлению к ближайшему свободному зазору (вправо или влево), освобождая нужное место. Когда зазоры вокруг какого-то участка заканчиваются (массив заполняется или сдвигать больше некуда), выполняется rebalance() - все текущие элементы перераспределяются заново, равномерно, в массиве увеличенной ёмкости.

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

Проверим заявленную экономию на конкретном входе. Возьмём массив [8, 3, 9, 1, 6, 4, 7, 2, 5] (n = 9) - тот же, что используется на вкладке «Визуализация». При capacity = max(9 * 2, 4) = 18 симуляция реализации из вкладки «Реализация» даёт: 17 сравнений бинарного поиска и 21 операцию сдвига на все 9 вставок вместе - в среднем 2.3 сдвига на вставку, а не 4-5, как было бы при линейном поиске места вставки в обычной сортировке вставками.

Число сдвигов сильно зависит от паттерна входа. На уже отсортированном [1..9] та же реализация делает 16 сравнений и 0 сдвигов - каждый новый максимум просто дописывается в следующую пустую ячейку справа. На развороте [9..1] - 21 сравнение и 36 сдвигов (в среднем 4 на вставку): каждый новый минимум должен протолкнуться через уже занятые ячейки к началу массива, зазоры на этой стороне быстро заканчиваются.

Отсюда видно, откуда берётся средняя O(n log n): бинарный поиск всегда стоит O(log(число заполненных ячеек)), независимо от порядка входа - это и даёт 16-21 сравнение на массиве из 9 элементов (9 * log₂9 ≈ 9 * 3.17 ≈ 28.5 - верхняя оценка с запасом). Сдвиги же - переменная часть: при случайном или сортированном входе они в среднем O(1) на вставку благодаря равномерно распределённым зазорам, но могут вырасти до O(n) на вставку при систематически однонаправленном заполнении, как в развороте.

Отдельный факт, который стоит проверить прямо в коде: при capacity = Math.max(n * 2, 4) (строка 5 на вкладке «Реализация») функция rebalance() не вызывается ни разу ни для одного из проверенных входов - ни для случайного, ни для отсортированного, ни для разворота, ни для массива из повторяющихся значений. Причина в арифметике: за весь проход count увеличивается максимум до n, а capacity не меньше 2n (или 4), поэтому условие count === capacity (строка 31) никогда не выполняется, а значит массив никогда не заполняется полностью и найти свободную ячейку слева или справа удаётся всегда.

Это отличает показанную реализацию от оригинального алгоритма из статьи Bender, Farach-Colton и Mosteiro (2004). Там ёмкость не фиксируется заранее с большим запасом - вместо этого используется схема «эпох»: массив периодически, раз в O(log n) вставок, полностью перестраивается с новой, растущей ёмкостью, что и даёт строгую амортизированную границу O(log n) на вставку в ожидании. Здесь же rebalance() оставлена как защитный код на случай другого выбора capacity, но при capacity = 2n она - мёртвый код: упрощение ради читаемости, отмеченное и в разделе «Минусы» на вкладке «Плюсы и минусы».

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

Библиотечную сортировку изобрели Майкл Бендер, Мартин Фарак-Колтон и Мигель Мостейро и опубликовали в 2004 году под названием «Insertion sort is O(n log n)» - намеренно провокационное название, обыгрывающее тот факт, что вставочная сортировка обычно ассоциируется исключительно с O(n²). Их результат показал, что тот же базовый механизм (сравнить и вставить) при добавлении зазоров и периодической перестройки даёт логарифмический множитель в ожидании, оставаясь при этом онлайн-алгоритмом - в отличие от сортировок, которым нужен весь массив целиком заранее.

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

Против обычной сортировки вставками - при одинаковой простоте реализации библиотечная сортировка выигрывает в константе на любом входе, кроме патологически однонаправленного заполнения; измеренные 21 сдвиг вместо потенциальных ~36 (как в развороте) на n = 9 показывают выигрыш уже на маленьких массивах.

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

При выборе размера начальной ёмкости - как показано в разборе выше, capacity = 2n делает rebalance() практически недостижимым; для настоящей амортизированной гарантии O(log n) нужна более плотная ёмкость (например, 1.1n) вместе с периодической перестройкой по эпохам, а не только «по требованию».

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

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

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

Gap buffer в текстовых редакторах (Emacs и многие другие) применяет ту же базовую идею - один большой зазор в месте курсора вместо распределённых по всему буферу, чтобы редактирование рядом с курсором стоило O(1), а не сдвига всего текста.

Система потоковой обработки графов Aspen (Dhulipala, Blelloch, Shun) использует массивы с зазорами (packed-memory arrays) в том же духе, что и библиотечная сортировка, для поддержания отсортированных списков смежности под непрерывным потоком обновлений графа.

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

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

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

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

• Оригинальная статья Bender, Farach-Colton и Mosteiro (2004) представила библиотечную сортировку как простую альтернативу балансированным деревьям поиска для задач поддержания отсортированного порядка при потоковой вставке элементов.
• Структуры данных с «дырявыми» массивами (gapped/packed-memory arrays) используются в базах данных и системах хранения столбцов для поддержания приблизительно отсортированного порядка без постоянной полной пересортировки.