раз. В сортировке методом вставок время выполнения задачи было возведено в квадрат, поскольку мы перемещали с места на место
n книг и сравнивали их с тем же количеством (
n) других книг прежде, чем выбрать место для очередной книги. Применение параметра линейного времени означает, что наши манипуляции с каждой книгой происходят в условиях постоянного времени вне зависимости от количества других книг, среди которых мы должны найти место каждой отдельной книге. Это отнюдь не похоже на правду.
Таким образом, мы знаем, что можем выполнять задачу в условиях квадратичного времени, но, вероятно, не линейного. Возможно, наш лимит находится где-то между линейным и квадратичным временем. Существуют ли какие-либо алгоритмы между линейным и квадратичным, между n и n × n?
Существуют и лежат на поверхности.
Как упоминалось ранее, процессы обработки информации были запущены в США во время проведения переписей населения в XIX веке в результате разработки Германом Холлеритом и впоследствии компанией IBM устройств по сортировке перфокарт. В 1936 году IBM приступила к производству линейки раскладочно-подборочных машин, которые могли объединить две отдельно упорядоченные стопки перфокарт в одну. Если каждая из пачек была разложена в верном порядке, то сам процесс их консолидации был невероятно простым и происходил в линейном времени: необходимо было просто сравнить две верхние карты из каждой стопки между собой, карту с наименьшим порядковым номером переместить в начало новой формируемой пачки и продолжать таким образом до выполнения задачи.
В программе, которую Джон фон Ньюманн написал в 1945 году, чтобы продемонстрировать преимущество ЭВМ с запоминаемой программой, была использована идея подборки и упорядочения перфокарт. Отсортировать две карты легко: просто переложите карту с меньшим порядковым номером поверх второй. И если у вас есть пара стопок по две карты каждая, сложенных в верном порядке, вы таким же способом можете легко сложить их в одну упорядоченную стопку из четырех карт. Повторяя этот прием несколько раз, вы будете получать все бóльшие и бóльшие стопки разложенных в нужном порядке карт. Довольно скоро вы соберете идеально упорядоченную стопку путем финального кульминационного объединения всех карт.
Этот подход сегодня известен как сортировка с объединением – один из легендарных алгоритмов компьютерной науки. Как было сказано в одной газете в 1997 году, «появление этого метода так же значимо в истории теории сортировки, как появление самой сортировки в истории развития программирования».