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

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

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

Целочисленная сортировка используется в одном из шести бенчмарков в наборе DARPA High Productivity Computing Systems Discrete Mathematics, и в одном из одиннадцати критериев NAS Parallel Benchmarks suite.

Источник: Википедия