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

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

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

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

13
задан osgx 4 August 2011 в 02:04
поделиться