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

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

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

Общие соображения [ править ]

Модели вычислений [ править ]

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

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

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

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

Сортировка по сравнению с очередями с целочисленным приоритетом [ править ]

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

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

Юзабилити [ править ]

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

Целочисленная сортировка обеспечивает один из шести тестов в наборе тестов DARPA High Productivity Computing Systems Discrete Mathematics [11] и один из одиннадцати тестов в пакете NAS Parallel Benchmarks .

Практические алгоритмы [ править ]

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

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

Теоретические алгоритмы [ править ]

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

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

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

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

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

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

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

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

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

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

Ранний результат в этом направлении был предоставлен Ajtai, Fredman & Komlós (1984) с использованием модели вычислений с использованием зондирования ячейки (искусственная модель, в которой сложность алгоритма измеряется только количеством обращений к памяти, которые он выполняет). Основываясь на своей работе, Фредман и Уиллард (1994) описали две структуры данных, Q-heap и атомарную кучу, которые можно реализовать на машине с произвольным доступом. Q-куча - это бит-параллельная версия двоичного дерева , которая позволяет выполнять операции с приоритетной очередью, а также запросы преемников и предшественников в постоянное время для наборов из O ((log N ) 1/4 ) элементов, где N ≤ 2w - размер предварительно вычисленных таблиц, необходимых для реализации структуры данных. Атомарная куча - этоB-дерево,в котором каждый узел дерева представлен как Q-куча; он позволяет выполнять операции очереди с постоянным приоритетом времени (и, следовательно, сортировку) для наборов(log N ) O (1) элементов.

Андерссон и др. (1998) предоставляют рандомизированный алгоритм, называемый сортировкой по сигнатуре, который позволяет выполнять линейную сортировку по времени наборов до 2 O ((log w ) 1/2 - ε ) элементов за раз для любой константы ε> 0 . Как и в алгоритме Киркпатрика и Райша, они выполняют сокращение диапазона, используя представление ключей в виде чисел с основанием  b для тщательного выбора b . Их алгоритм сокращения диапазона заменяет каждую цифру подписью, которая представляет собой хешированное значение с O (log n ) бит, так что разные значения цифр имеют разные подписи. Если пдостаточно мало, числа, сформированные этим процессом замены, будут значительно меньше, чем исходные ключи, что позволяет неконсервативному алгоритму упакованной сортировки Albers & Hagerup (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 ), либо рандомизации в виде хеш-таблиц. [17]

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

Ссылки [ править ]

Сноски
  1. ^ а б Хан и Торуп (2002) .
  2. ^ Фредман & Willard (1993) .
  3. ^ Вопрос о том, следует ли разрешать операции целочисленного умножения или поиска в таблице, восходит к Фредману и Уилларду (1993) ; см. также Andersson, Miltersen & Thorup (1999) .
  4. ^ Рейф (1985) ; комментарий в Cole & Vishkin (1986) ; Hagerup (1987) ; Bhatt et al. (1991) ; Альберс и Хагеруп (1997) .
  5. ^ Аггарваль & Виттер (1988) .
  6. ^ Фархади и др. (2020) .
  7. ^ а б Чоудхури (2008) .
  8. ^ Макилрой, Бостик и Макилрой (1993) ; Андерссон и Нильссон (1998) .
  9. ^ a b Рахман и Раман (1998) .
  10. Перейти ↑ Pedersen (1999) .
  11. ^ DARPA HPCS Discrete Mathematics Benchmarks , Дункан А. Буэлл, Университет Южной Каролины, получено 2011-04-20.
  12. ^ Goodrich & Tamassia (2002) . Хотя Cormen et al. (2001) также описывают версию этого алгоритма сортировки, версия, которую они описывают, адаптирована для входных данных, где ключи являются действительными числами с известным распределением, а не для целочисленной сортировки.
  13. ^ Кормен и др. (2001) , 8.2 Сортировка подсчета, стр. 168–169.
  14. ↑ Комри (1929–1930) ; Cormen et al. (2001) , 8.3 Radix Sort, стр. 170–173.
  15. ^ Киркпатрик и Райш (1984) ; Альберс и Хагеруп (1997) .
  16. ^ Киркпатрик и Райш (1984) .
  17. ^ Андерссон и др. (1998) .
  18. ↑ Хан (2004) .
  19. ^ Thorup (2002)
Вторичные источники
  • Чоудхури, Резаул А. (2008), «Эквивалентность между приоритетными очередями и сортировкой» , в Као, Мин-Янг (ред.), Энциклопедия алгоритмов , Springer, стр. 278–281, ISBN. 9780387307701.
  • Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001), Введение в алгоритмы (2-е изд.), MIT Press и McGraw-Hill , ISBN 0-262-03293-7.
  • Гудрич, Майкл Т .; Тамассия, Роберто (2002), «4.5 Bucket-Sort and Radix-Sort», Разработка алгоритмов: основы, анализ и Интернет-примеры , John Wiley & Sons, стр. 241–243.
Основные источники
  • Аггарвал, Алок; Виттер, Джеффри С. (сентябрь 1988), "Ввод / вывод сложность сортировки и связанных с ними задач", коммуникаций ACM , 31 (9): 1116-1127, DOI : 10,1145 / 48529,48535
  • Аджтай, М .; Фредман, М .; Комлоша, J. (1984), "Хеш - функция для очередей приоритетов", информация и управление , 63 (3): 217-225, DOI : 10.1016 / S0019-9958 (84) 80015-7 , МР  0837087.
  • Альберс, Сюзанна ; Хагеруп, Торбен (1997), "Улучшенное параллельное целое число без сортировки одновременной записи", информации и вычислений , 136 (1): 25-51, CiteSeerX  10.1.1.53.498 , DOI : 10,1006 / inco.1997.2632 , МР  1457693.
  • Андерссон, Арне; Хагеруп, Торбен; Нильссон, Стефан; Раман, Раджив (1998), "Сортировка в линейном времени?", Журнал компьютерных и системных наук , 57 (1): 74-93, DOI : 10,1006 / jcss.1998.1580 , MR  1649809.
  • Андерссон, Арне; Нильссон, Стефан (1998), «Реализация радикальной сортировки», ACM Journal of Experimental Algorithmics , 3 : 7 – es, CiteSeerX  10.1.1.54.4536 , doi : 10.1145 / 297096.297136 , MR  1717389.
  • Андерссон, Арне; Милтерсен, Питер Бро; Thorup, Миккель (1999), "Fusion дерева могут быть реализованы с помощью AC 0 инструкции только", теоретическая информатика , 215 (1-2): 337-344, CiteSeerX  10.1.1.32.9401 , DOI : 10.1016 / S0304-3975 ( 98) 00172-8 , MR  1678804.
  • Бхатт, PCP; Дикс, К .; Hagerup, T .; Прасад, VC; Радзик, Т .; Саксена, С. (1991), "Улучшенное детерминированным параллельное число сортировки", информации и вычислений , 94 (1): 29-47, DOI : 10.1016 / 0890-5401 (91) 90031-В , МР  1123154.
  • Cole, R .; Vishkin, У. (1986), "Детерминированная монета бросание с приложениями к оптимальному списку параллельного рейтинга", информация и управление , 70 (1): 32-53, DOI : 10.1016 / S0019-9958 (86) 80023-7.
  • Комри, LJ (1929–1930), "Табуляторы Холлерита и Пауэрса", Trans. Офис Mach. Пользовательская ассоциация, ООО : 25–37. Цитируется Thorup (2007) как один из первых источников для сортировки по основанию .
  • Фархади, Алиреза; Хаджиагайи, Мохаммад Таги ; Ларсен, Каспер Грин; Ши, Элейн (сентябрь 2020 г.), «Нижние границы для целочисленной сортировки внешней памяти через сетевое кодирование», Коммуникации ACM , 63 (10): 97–105, arXiv : 1811.01313 , doi : 10.1145 / 3416268.
  • Фредман, Майкл Л .; Willard, Dan E. (1993), "Превосходя информационно-Теоретико связаны с слитых деревьев", журнал компьютерных и системных наук , 47 (3): 424-436, DOI : 10.1016 / 0022-0000 (93) 90040-4 , Руководство пользователя  1248864.
  • Фредман, Майкл Л .; Willard, Dan E. (1994), "Транс-дихотомические алгоритмы минимальных остовных деревьев и кратчайшие пути", журнал компьютерных и системных наук , 48 (3): 533-551, DOI : 10.1016 / S0022-0000 (05) 80064 -9 , Руководство по ремонту  1279413.
  • Hagerup, Torben (1987), «На пути к оптимальной параллельной сортировке ведра», Информация и вычисления , 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.
  • Хан, Ицзе; Thorup, M. (2002), "Целочисленная сортировка в O ( n √ log log n ) ожидаемом времени и линейном пространстве", Труды 43-го ежегодного симпозиума по основам компьютерных наук (FOCS 2002) , IEEE Computer Society, стр. 135 –144, DOI : 10.1109 / SFCS.2002.1181890.
  • Киркпатрик, Дэвид ; Reisch, Стефан (1984), "Верхние границы для сортировки целых чисел на машинах с произвольным доступом", теоретическая информатика , 28 (3): 263-276, DOI : 10,1016 / 0304-3975 (83) 90023-3 , MR  0742289.
  • Макилрой, Питер М .; Бостик, Кейт; Макилрой, М. Дуглас (1993), "Engineering Radix Sort" (PDF) , Computing Systems , 6 (1): 5–27.
  • Педерсен, Мортен Николай (1999), Исследование практического значения алгоритмов ОЗУ слов для внутренней целочисленной сортировки , магистерская диссертация, Департамент компьютерных наук, Университет Копенгагена, Дания, заархивировано из оригинала 16 марта 2012 г. , извлечено из 2011 г. -04-21.
  • Рахман, Наиля; Раман, Раджив (1998), "Экспериментальное исследование параллелизма на уровне слов в некоторых алгоритмах сортировки", Разработка алгоритмов, 2-й международный семинар, WAE '92, Саарбрюккен, Германия, 20–22 августа 1998 г., Proceedings (PDF) , Max Институт компьютерных наук Планка , стр. 193–203..
  • Рейф, Джон Х. (1985), «Оптимальный параллельный алгоритм для целочисленной сортировки», Труды 26-го ежегодного симпозиума по основам компьютерных наук (FOCS 1985) , IEEE Computer Society, стр. 496–504, doi : 10.1109 / SFCS 1985,9.
  • Thorup, Mikkel (2002), «Рандомизированная сортировка во времени O ( n log log n ) и линейном пространстве с использованием сложения, сдвига и побитовых логических операций», Journal of Algorithms , 42 (2): 205–230, CiteSeerX  10.1 .1.55.4443 , DOI : 10,1006 / jagm.2002.1211 , МР  1895974.
  • Thorup, Mikkel (2003), "О реализациях AC 0 деревьев слияния и атомных кучек", Труды четырнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (Балтимор, Мэриленд, 2003) , Нью-Йорк: ACM, стр. 699–707 , MR  1974982.
  • Thorup, Mikkel (2007), «Эквивалентность между приоритетными очередями и сортировкой», Журнал ACM , 54 (6): Art. 28, DOI : 10,1145 / 1314690,1314692 , МР  2374029.
  • Уиллард, Дэн Э. (1983), «Логарифмические запросы диапазона наихудшего случая возможны в пространстве Θ ( N ) », Письма об обработке информации , 17 (2): 81–84, DOI : 10.1016 / 0020-0190 (83 ) 90075-3 , Руководство по ремонту  0731126.