Целочисленная сортировка

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

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

Общие соображения

Модели вычислений

Временные ограничения для алгоритмов сортировки целых чисел обычно зависят от трех параметров: количества n значений данных, подлежащих сортировке, величины K наибольшего возможного ключа, подлежащего сортировке, и количества w бит, которые могут быть представлены в одном машинном слове компьютер, на котором будет выполняться алгоритм. Обычно предполагается, что w ≥ log ₂ (max( n , K )) ; то есть машинные слова достаточно велики, чтобы представлять индекс в последовательности входных данных, а также достаточно велики, чтобы представлять один ключ.

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

Андерссон, Милтерсен и Торуп (1999) показали, что в некоторых случаях умножения или поиск в таблицах, необходимые для некоторых алгоритмов целочисленной сортировки, можно заменить специальными операциями, которые легче реализовать на аппаратном уровне, но которые обычно недоступны на компьютерах общего назначения. Торуп (2003) улучшил эту ситуацию, показав, как заменить эти специальные операции инструкциями по манипуляции битовыми полями , уже доступными в процессорах Pentium .

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

Сортировка и очереди с целочисленным приоритетом

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

Вместо использования очереди с целочисленным приоритетом в алгоритме сортировки можно пойти в другом направлении и использовать алгоритмы целочисленной сортировки в качестве подпрограмм в структуре данных очереди с целочисленным приоритетом. Торуп (2007) использовал эту идею, чтобы показать, что если можно выполнить целочисленную сортировку за время T ( n ) для каждого ключа, то такая же временная граница применяется ко времени на операцию вставки или удаления в структуре данных очереди с приоритетом. Редукция Торупа сложна и предполагает наличие либо быстрых операций умножения, либо поиска по таблицам, но он также предоставляет альтернативную приоритетную очередь, используя только сложение и логические операции со временем T ( n ) + T (log n ) + T (log log n ) + ... за операцию, максимум умножая время на повторный логарифм .

Удобство использования

Классические алгоритмы сортировки целых чисел, такие как сортировка по ячейкам , сортировка по подсчету и поразрядная сортировка, широко используются и практичны. Большая часть последующих исследований алгоритмов сортировки целых чисел была сосредоточена не столько на практичности, сколько на теоретических усовершенствованиях анализа наихудших случаев , и алгоритмы, возникшие в этом направлении исследований, не считаются практичными для современных 64-битных компьютерных архитектур, хотяэксперименты показали, что некоторые из этих методов могут улучшить поразрядную сортировку данных со 128 или более битами на ключ. Кроме того, для больших наборов данных шаблоны почти случайного доступа к памяти многих алгоритмов целочисленной сортировки могут препятствовать им по сравнению с алгоритмами сортировки сравнения, которые были разработаны с иерархии памяти . учетом

Целочисленная сортировка представляет собой один из шести тестов в наборе тестов дискретной математики DARPA для высокопроизводительных вычислительных систем . и один из одиннадцати тестов в наборе NAS Parallel Benchmarks .

Практические алгоритмы

Сортировка по ячейкам или сортировка с подсчетом могут сортировать n элементов данных, имеющих ключи в диапазоне от 0 до K -1, за время O ( n + K ) . При сортировке по ячейкам (часто называемой сортировкой по сегментам) указатели на элементы данных распределяются по таблице сегментов, представленной в виде типов данных коллекции , таких как связанные списки , с использованием ключей в качестве индексов в таблице. Затем все сегменты объединяются вместе, чтобы сформировать выходной список. Сортировка по подсчету использует таблицу счетчиков вместо таблицы сегментов, чтобы определить количество элементов с каждым ключом. Затем вычисление суммы префиксов используется для определения диапазона позиций в отсортированном выводе, в которых должны быть размещены значения с каждым ключом. Наконец, при втором проходе входных данных каждый элемент перемещается на позицию своего ключа в выходном массиве. Оба алгоритма включают в себя только простые циклы по входным данным (занимающие время O ( n ) ) и набору возможных ключей ( затрачивающие время O ( K ) ), давая их O ( n + K ) общее время .

Поразрядная сортировка — это алгоритм сортировки, который работает для более крупных ключей, чем сортировка по ячейкам или сортировка по подсчету, выполняя несколько проходов по данным. Каждый проход сортирует входные данные, используя только часть ключей, используя другой алгоритм сортировки (например, сортировку по ячейкам или сортировку с подсчетом), который подходит только для маленьких ключей. Чтобы разбить ключи на части, алгоритм поразрядной сортировки вычисляет позиционное обозначение для каждого ключа:по какому-то выбранному основанию ; тогда часть ключа, используемая для i -го прохода алгоритма, представляет собой i -ю цифру в позиционной записи полного ключа, начиная с наименее значащей цифры и продвигаясь к наиболее значимой. Чтобы этот алгоритм работал корректно, алгоритм сортировки, используемый при каждом проходе по данным, должен быть стабильным : элементы с одинаковыми цифрами не должны менять позиции друг с другом. Для наибольшей эффективности систему счисления следует выбирать так, чтобы она была близка количеству элементов данных n . Кроме того, использование степени двойки рядом с n в качестве системы счисления позволяет быстро вычислять ключи для каждого прохода, используя только быстрые операции двоичного сдвига и маски. При таком выборе, а также сортировке по ячейкам или сортировке подсчетом в качестве базового алгоритма алгоритм поразрядной сортировки может сортировать n элементов данных, имеющих ключи в диапазоне от 0 до K −1 за время O ( n log _n K ) .

Теоретические алгоритмы

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

Алгоритмы для маленьких ключей

Дерево Ван-Эмде-Боаса можно использовать в качестве приоритетной очереди для сортировки набора из n ключей, каждый из которых находится в диапазоне от 0 до K - 1 , за время O ( n log log K ) . Это теоретическое улучшение по сравнению с поразрядной сортировкой, когда K достаточно велико. Однако, чтобы использовать дерево Ван Эмде Боаса, либо нужна непосредственно адресуемая память из K слов, либо нужно смоделировать ее с помощью хеш-таблицы , уменьшая пространство до линейного, но делая алгоритм рандомизированным. Другая приоритетная очередь с аналогичной производительностью (включая необходимость рандомизации в виде хеш-таблиц) — это Y-быстрое дерево Уилларда (1983) .

Более сложная методика с аналогичным подходом и лучшими теоретическими характеристиками была разработана Киркпатриком и Райшем (1984) . раз Они заметили, что каждый проход поразрядной сортировки можно интерпретировать как метод сокращения диапазона, который за линейное время уменьшает максимальный размер ключа в n ; вместо этого их метод уменьшает размер ключа до квадратного корня из его предыдущего значения (уменьшая вдвое количество битов, необходимых для представления ключа), опять же за линейное время. Как и при поразрядной сортировке, они интерпретируют ключи как двузначные числа по основанию b для основания b, которое приблизительно равно √ K . Затем они группируют элементы, подлежащие сортировке, в корзины в соответствии с их старшими цифрами в линейном времени, используя либо большую, но неинициализированную память с прямой адресацией, либо хеш-таблицу. У каждого ведра есть представитель — предмет в ведре с самым большим ключом; затем они сортируют список элементов, используя в качестве ключей старшие цифры для представителей и младшие цифры для непредставителей. Снова сгруппировав элементы из этого списка в сегменты, каждый сегмент можно расположить в отсортированном порядке, а путем извлечения представителей из отсортированного списка сегменты можно объединить в отсортированный порядок. Таким образом, за линейное время проблема сортировки сводится к другой задаче рекурсивной сортировки, в которой ключи намного меньше — квадратный корень из их предыдущей величины. Повторение этого сокращения диапазона до тех пор, пока ключи не станут достаточно маленькими для сортировки сегментов, приводит к алгоритму с временем выполнения. O( n журнал журнал _n K ) .

Сложный рандомизированный алгоритм Хана и Торупа (2002) в Word RAM модели вычислений позволяет еще больше сократить эти временные границы до O( n √ log log K ) .

Алгоритмы для больших слов

Алгоритм сортировки целых чисел называется неконсервативным, если он требует размера слова w , который значительно больше, чем log max( n , K ) . В крайнем случае, если w ≥ K и все ключи различны, то набор ключей можно отсортировать за линейное время, представляя его в виде битового вектора с 1 битом в позиции i , когда i является одним из входных ключей, а затем неоднократно удаляя младший бит.

Неконсервативный алгоритм пакетной сортировки Альберса и Хагерупа (1997) использует подпрограмму, основанную на Кена Бэтчера , сети битонной сортировки для слияния двух отсортированных последовательностей ключей, каждая из которых достаточно коротка, чтобы быть упакованной в одно машинное слово. Входные данные для алгоритма упакованной сортировки, последовательность элементов, хранящихся по одному на слово, преобразуются в упакованную форму, последовательность слов, каждое из которых содержит несколько элементов в отсортированном порядке, путем многократного использования этой подпрограммы для удвоения количества элементов, упакованных в каждый. слово. Когда последовательность находится в упакованной форме, Альберс и Хагеруп используют для ее сортировки сортировку слиянием ; когда две последовательности объединяются в одну более длинную последовательность, можно использовать одну и ту же процедуру битонической сортировки для многократного извлечения упакованных слов, состоящих из наименьших оставшихся элементов двух последовательностей. Этот алгоритм получает достаточное ускорение от своего упакованного представления, чтобы сортировать входные данные за линейное время всякий раз, когда одно слово может содержать Ω(log n log log n ) ключи; то есть, когда log K log n log log n ≤ cw для некоторой константы c > 0 .

Алгоритмы для нескольких предметов

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

Ранний результат в этом направлении был получен Айтаи, Фредманом и Комлосом (1984) с использованием модели вычислений с ячейковым зондом (искусственная модель, в которой сложность алгоритма измеряется только количеством выполняемых им обращений к памяти). Основываясь на своей работе, Фредман и Уиллард (1994) описали две структуры данных: Q-кучу и атомную кучу, которые можно реализовать на машине с произвольным доступом. Q-куча — это побитово-параллельная версия двоичного дерева , которая позволяет выполнять как операции приоритетной очереди, так и запросы к преемнику и предшественнику за постоянное время для наборов O ((log N ) ^1/4 ) элементы, где N ≤ 2 ^В — это размер предварительно вычисленных таблиц, необходимых для реализации структуры данных. Атомная куча — это B-дерево , в котором каждый узел дерева представлен как Q-куча; он позволяет выполнять операции с очередью с постоянным приоритетом времени (и, следовательно, сортировку) для наборов (log N ) ^{О (1)} предметы.

Андерссон и др. (1998) представили рандомизированный алгоритм, называемый сортировкой по сигнатурам, который позволяет сортировать наборы размером до 2 по линейному времени. ^{O ((log w ) 1/2 - е )} элементы одновременно, для любой константы ε > 0 . Как и в алгоритме Киркпатрика и Райша, они выполняют сокращение диапазона, используя представление ключей в виде чисел по основанию b для тщательного выбора b . Их алгоритм сокращения диапазона заменяет каждую цифру сигнатурой, которая представляет собой хешированное значение с битами O (log n ), так что разные значения цифр имеют разные подписи. Если n достаточно мало, числа, сформированные в результате этого процесса замены, будут значительно меньше, чем исходные ключи, что позволит неконсервативному алгоритму пакетной сортировки Альберса и Хагерупа (1997) сортировать замененные числа за линейное время. Из отсортированного списка замененных чисел можно сформировать сжатое дерево ключей за линейное время, а дочерние элементы каждого узла дерева можно рекурсивно сортировать, используя только ключи размера b , после чего обход дерева дает отсортированный порядок элементов.

Трансдихотомические алгоритмы

Фредман и Уиллард (1993) представили трансдихотомическую модель анализа алгоритмов целочисленной сортировки, в которой ничего не предполагается о диапазоне целочисленных ключей и необходимо ограничивать производительность алгоритма функцией только количества значений данных. , что время работы алгоритма на наборе из n Альтернативно, в этой модели предполагается элементов — это время работы в наихудшем случае для любой возможной комбинации значений K и w . Первым алгоритмом этого типа был алгоритм сортировки слитного дерева Фредмана и Уилларда , который работает за время O( n log n / log log n ) ; это улучшение по сравнению со сравнительной сортировкой для любого выбора K и w . Альтернативная версия их алгоритма, включающая использование случайных чисел и операций целочисленного деления, улучшает его до O( n √ log n ) .

Со времени их работы были разработаны еще более совершенные алгоритмы. Например, многократно применяя метод сокращения диапазона Киркпатрика-Райша до тех пор, пока ключи не станут достаточно маленькими, чтобы применить алгоритм пакетной сортировки Альберса-Хагерупа, можно выполнить сортировку за время O ( n log log n ) ; однако часть этого алгоритма, связанная с уменьшением диапазона, требует либо большого объема памяти (пропорционального √ K ), либо рандомизации в форме хеш-таблиц.

Хан и Торуп (2002) показали, как сортировать за рандомизированное время O( n √ log log n ) . Их метод предполагает использование идей, связанных с сортировкой сигнатур, для разделения данных на множество небольших подсписков достаточно маленького размера, чтобы сортировка сигнатур могла эффективно сортировать каждый из них. Также можно использовать аналогичные идеи для детерминированной сортировки целых чисел во времени O ( n log log n ) и линейном пространстве. Используя только простые арифметические операции (без умножения или поиска в таблице), можно сортировать в случайном ожидаемом времени O ( n log log n ). или детерминированно за время O ( n (log log n ) ^{1 + е} ) для любой константы ε > 0 .

Ссылки

Сноски

Вторичные источники

• Чоудхури, Резаул А. (2008), «Эквивалентность между приоритетными очередями и сортировкой» , в Као, Минг-Янг (редактор), Энциклопедия алгоритмов , Springer, стр. 278–281, ISBN  9780387307701 .
• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001), Введение в алгоритмы (2-е изд.), MIT Press и McGraw-Hill , ISBN  0-262-03293-7 .
• Гудрич, Майкл Т .; Тамассиа, Роберто (2002), «4.5 Bucket-Sort и Radix-Sort», Разработка алгоритмов: основы, анализ и примеры из Интернета , John Wiley & Sons, стр. 241–243 .

Первоисточники

• Аггарвал, Алок; Виттер, Джеффри С. (сентябрь 1988 г.), «Сложность ввода-вывода при сортировке и связанные с ней проблемы», Communications of the ACM , 31 (9): 1116–1127, doi : 10.1145/48529.48535 , S2CID   6264984
• Аджтай, М. ; Фредман, М .; Комлос, Дж. (1984), «Хеш-функции для приоритетных очередей», Information and Control , 63 (3): 217–225, doi : 10.1016/S0019-9958(84)80015-7 , MR   0837087 .
• Альберс, Сюзанна ; Хагеруп, Торбен (1997), «Улучшенная параллельная сортировка целых чисел без одновременной записи», Information and Computation , 136 (1): 25–51, CiteSeerX   10.1.1.53.498 , doi : 10.1006/inco.1997.2632 , MR   1457693 , S2CID   1284673 .
• Андерссон, Арне; Хагеруп, Торбен; Нильссон, Стефан; Раман, Раджив (1998), «Сортировка в линейном времени?», Журнал компьютерных и системных наук , 57 (1): 74–93, doi : 10.1006/jcss.1998.1580 , MR   1649809 .
• Андерссон, Арне; Нильссон, Стефан (1998), «Реализация поразрядной сортировки», Журнал экспериментальной алгоритмики ACM , 3 :7–es, CiteSeerX   10.1.1.54.4536 , doi : 10.1145/297096.297136 , MR   1717389 , S2CID   2125652 .
• Андерссон, Арне; Милтерсен, Питер Бро; Торуп, Миккель (1999), «Деревья слияния могут быть реализованы с помощью AC ⁰ только инструкции», Theoretical Computer Science , 215 (1–2): 337–344, CiteSeerX   10.1.1.32.9401 , doi : 10.1016/S0304-3975(98)00172-8 , MR   1678804 .
• Бхатт, PCP; Дикс, К.; Хагеруп, Т.; Прасад, ВК; Радзик Т.; Саксена, С. (1991), «Улучшенная детерминированная параллельная целочисленная сортировка», Information and Computation , 94 (1): 29–47, doi : 10.1016/0890-5401(91)90031-V , MR   1123154 .
• Коул, Р.; Вишкин, У. (1986), «Детерминистическое подбрасывание монеты с применением оптимального ранжирования параллельных списков», Information and Control , 70 (1): 32–53, doi : 10.1016/S0019-9958(86)80023-7 .
• Комри, LJ (1929–1930), «Счетные машины Холлерита и Пауэрса», Пер. Офис Маха. Ассоциация пользователей, ООО. : 25–37 . Цитируется Торупом (2007) как один из первых источников поразрядной сортировки .
• Фархади, Алиреза; Хаджиагайи, Мохаммад Таги ; Ларсен, Каспер Грин; Ши, Элейн (сентябрь 2020 г.), «Нижние границы сортировки целых чисел во внешней памяти посредством сетевого кодирования», Communications of the ACM , 63 (10): 97–105, arXiv : 1811.01313 , doi : 10.1145/3416268 , S2CID   221865838 .
• Фредман, Майкл Л .; Уиллард, Дэн Э. (1993), «Преодоление теоретико-информационной связи с объединенными деревьями», Journal of Computer and System Sciences , 47 (3): 424–436, doi : 10.1016/0022-0000(93)90040-4 , МР   1248864 .
• Фредман, Майкл Л .; Уиллард, Дэн Э. (1994), «Трансдихотомические алгоритмы для минимальных остовных деревьев и кратчайших путей», Журнал компьютерных и системных наук , 48 (3): 533–551, doi : 10.1016/S0022-0000(05)80064 -9 , МР   1279413 .
• Хагеруп, Торбен (1987), «На пути к оптимальной параллельной сортировке ведер», Information and Computation , 75 (1): 39–51, doi : 10.1016/0890-5401(87)90062-9 , MR   0910976 .
• Хан, Ицзе (2004), «Детерминированная сортировка во времени O ( n log log n ) и линейном пространстве», Journal of Algorithms , 50 (1): 96–105, doi : 10.1016/j.jalgor.2003.09.001 , MR   2028585 .
• Хан, Ицзе; Торуп, М. (2002), «Целочисленная сортировка в ожидаемом времени O( n √ log log n ) и линейном пространстве», Труды 43-го ежегодного симпозиума по основам компьютерных наук (FOCS 2002) , Компьютерное общество IEEE, стр. 135 –144, doi : 10.1109/SFCS.2002.1181890 , S2CID   5245628 .
• Киркпатрик, Дэвид ; Райш, Стефан (1984), «Верхние границы сортировки целых чисел на машинах с произвольным доступом», Theoretical Computer Science , 28 (3): 263–276, doi : 10.1016/0304-3975(83)90023-3 , MR   0742289 .
• Макилрой, Питер М.; Бостик, Кейт; Макилрой, М. Дуглас (1993), «Инженерная поразрядная сортировка» (PDF) , Вычислительные системы , 6 (1): 5–27 .
• Педерсен, Мортен Николай (1999), Исследование практической значимости алгоритмов словесного ОЗУ для внутренней целочисленной сортировки , магистерская диссертация, факультет компьютерных наук, Копенгагенский университет, Дания, заархивировано из оригинала 16 марта 2012 г. , получено в 2011 г. -04-21 .
• Рахман, Наиля; Раман, Раджив (1998), «Экспериментальное исследование параллелизма на уровне слов в некоторых алгоритмах сортировки», Разработка алгоритмов, 2-й международный семинар, WAE '92, Саарбрюккен, Германия, 20–22 августа 1998 г., Материалы (PDF) , Макс Институт компьютерных наук Планка , стр. 193–203 .
• Рейф, Джон Х. (1985), «Оптимальный параллельный алгоритм для сортировки целых чисел», Труды 26-го ежегодного симпозиума по основам информатики (FOCS 1985) , IEEE Computer Society, стр. 496–504, doi : 10.1109/SFCS .1985.9 , ISBN  0-8186-0644-4 , S2CID   5694693 .
• Торуп, Миккель (2002), «Рандомизированная сортировка во времени O ( n log log n ) и линейном пространстве с использованием сложения, сдвига и побитовых логических операций», Journal of Algorithms , 42 (2): 205–230, CiteSeerX   10.1 .1.55.4443 , номер документа : 10.1006/jagm.2002.1211 , MR   1895974 , S2CID   9700543 .
• Торуп, Миккель (2003), "На переменном токе ⁰ реализации деревьев слияния и атомных куч», Труды четырнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (Балтимор, Мэриленд, 2003 г.) , Нью-Йорк: ACM, стр. 699–707, ISBN  978-0-89871-538-5 , МР   1974982 .
• Торуп, Миккель (2007), «Эквивалентность очередей с приоритетами и сортировкой», Журнал ACM , 54 (6): Ст. 28, номер домена : 10.1145/1314690.1314692 , MR   2374029 .
• Уиллард, Дэн Э. (1983), «Лог-логарифмические запросы диапазона наихудшего случая возможны в пространстве Θ( N ) », Information Processing Letters , 17 (2): 81–84, doi : 10.1016/0020-0190(83) )90075-3 , МР   0731126 .