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

Question

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

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

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

Answer 1

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

Answer 2

Сортировка подписи хороша для больших размеров слов с ожидаемой сложностью времени 'O (n lg lg n)', но с небольшими размерами слов вы можете получить ту же сложность с сортировкой фон Эмде Боаса. Также недавно были опубликованы еще более быстрый алгоритм сортировки от Хана и Торапа с ожидаемой временной сложностью 'O (n sqrt (lg lg n)) ". Я не уверен, сможете ли вы найти реализации этих алгоритмов онлайн, но, вероятно, есть несколько замечательных статей и лекций по MIT и Гарварду.

Answer 3

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

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

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

Answer 4

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