Истоки Radix sorting.

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

Radix sorting, или поразрядная сортировка, заключается в том, что мы сначала делим данные по разрядам, а потом сортируем их внутри каждого разряда. Процесс сортировки может начинаться как с младших (правых), так и со старших (левых) разрядов. Первый подход известен как LSD-сортировка (Least Significant Digit radix sort), второй — как MSD-сортировка (Most Significant Digit radix sort). 

В реальных задачах поразрядная сортировка часто оказывается быстрее алгоритмов сортировки на основе сравнений, но она не так эффективна для небольших наборов данных. Кстати, на разряды можно разделить не только числа, но и, например, строки для поразрядной сортировки. 

Появление radix sorting связывают с 1887 годом, когда Герман Холлерит подал патент на электромеханическую табуляционную машину для обработки перфокарт. Инновационный подход и такие машины использовались в ходе переписи населения США 1890 года, а позднее — и в Российской империи для аналогичных задач.