«Проблема с носками ставит меня в тупик!» – признался легендарный специалист по криптографии и информатике, лауреат премии Тьюринга Рон Ривест, когда мы заговорили с ним об этом вопросе.
Во время встречи на нем были сандалии на босу ногу.
Сортировка лежит в основе работы компьютеров. По сути, именно необходимость сортировки послужила причиной создания компьютера.
В конце XIX века прирост населения Соединенных Штатов составлял 30 % за десятилетие, и количество «объектов исследования» Бюро переписи населения за 10 лет с 1870 по 1880 год возросло с пяти до более чем двухсот. Подведение итогов переписи 1880 года заняло восемь лет, и почти сразу после окончания работ стартовала перепись 1890 года.
Как выразился один писатель того времени, было удивительно, как «канцелярские работники, заваленные бессчетным количеством бумаг… не ослепли и не сошли с ума».
Само ведомство едва не рухнуло под собственным весом. Нужно было срочно что-то делать.
Вдохновленный существовавшей в то время системой компостирования железнодорожных билетов изобретатель Герман Холлерит решил использовать технологию компостирования карточек из манильской бумаги для хранения информации. Для учета и сортировки карточек им была изобретена первая табулирующая машина, которая позднее была названа его именем. Он получил патент на устройство в 1889 году, а уже в 1890-м машина Холлерита была одобрена правительством для использования при переписи населения. До этого никто не видел ничего подобного.
Восхищенный обозреватель писал: «Этот аппарат работает с божественной точностью, но по скорости превосходит даже высшие силы». Другой обозреватель тем не менее отметил, что область применения машины ограничена и «изобретатель вряд ли разбогатеет на этом устройстве, поскольку никто кроме правительства не станет его использовать». Этому прогнозу, который Холлерит взял на заметку, не было суждено сбыться в точности. Фирма Холлерита объединилась с рядом других компаний в 1911 году и вошла в промышленный конгломерат CTR (Computing-Tabulating-Recording Company). Спустя несколько лет компания была переименована в IBM (International Business Machines).
Техника сортировки продолжала подстегивать развитие компьютерной науки на протяжении следующего столетия. Первым в мире кодом, написанным для ЭВМ с запоминаемой программой, стала программа для эффективной сортировки. В сущности, именно способность компьютера заменить аппараты IBM, заточенные исключительно под сортировку перфокарт, убедила американское правительство в том, что колоссальные инвестиции в создание универсальной машины оправданны.