Быстрая реализация целочисленной сортировки для 200-300 бит целых чисел?

Какова самая быстрая реализация целочисленной сортировки для целых чисел размером 200-300 бит? Исправлен точный размер int; У меня есть до 2 гигабайт с такими целыми числами (все в ОЗУ).

Я слышал, что можно сортировать такой набор в среднем по O (n log log M) или даже по времени O (n sqrt (log log M)), wher n - число целых чисел, а M - наибольшее целое число, Использование памяти ограничено (я могу использовать до 0,5-1 ГБ дополнительно). Сортировка может выполняться на месте; in могут быть неустойчивыми (переупорядочить дубликаты).

Существует ли реализация C/С++ такого метода сортировки, например. Хан и Торуп (2002)?

Ответ 1

A Radix Sort можно использовать для сортировки данных с помощью ключей фиксированного размера. Поскольку это условие не часто встречается, метод не обсуждается много, но он может быть O (n), когда размер ключа учитывается.

Ответ 2

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

Ответ 3

Сортировка подписи хороша с большими размерами слов с "сложной сложностью времени" O (n lg lg n) ", но с небольшими размерами слов вы можете получить такую же сложность с помощью сортировки Vem Emde Boas. Также недавно был опубликован еще более быстрый алгоритм сортировки от Han и Thorup с ожидаемой сложностью времени" O (n sqrt (lg lg n))". Я не уверен, что вы можете найти реализации этих алгоритмов в Интернете, но, вероятно, есть несколько замечательных статей и лекций по MIT и Harvard.

Ответ 4

Я думаю, что наиболее разумным является создание массива указателей на bigints и сортировка массива указателей. Я бы предложил какой-то шаблонный quicksort с умной функцией сравнения.

Функция сравнения должна быть в состоянии решить большую часть времени, просмотрев наиболее важные 4 байта. Если они не совпадают, тогда будет определено сравнение. Если они совпадают, вы просматриваете следующие 4 байта до конца int.

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