Sorting by Merging

Во время лекции 1946 года в школе Мура один из разработчиков ENIAC Джон Мокли (John Mauchly) заметил:

Требование, чтобы одна машина объединяла возможности вычислений и сортировки, может выглядеть как требование, чтобы один прибор использовался как ключ для консервов и как авторучка.

Ещё он отметил, что сортировка необходима для выполнения математических процедур и численных расчетов. А сама лекция была посвящена «сортировке слиянием». 

Сортировка слиянием отрабатывает с одинаковой скоростью на любых массивах одинаковой длины, а временная сложность этого алгоритма — O(N log N). Идея сортировки слиянием в следующем:

1. Входной массив рекурсивно делится до подмассивов размером в один элемент, который считается отсортированным.

2. Элементы в подмассивах сравниваются попарно и заносятся по порядку. Они последовательно объединяются до получения одного отсортированного массива. 

Сортировка слиянием стала одним из первых алгоритмов, разработанных в парадигме «разделяй и властвуй», когда задача разбивается на более мелкие, а ответ собирается из их решений. Сам алгоритм был написан для первого компьютера с хранимой в памяти программой — EDVAC. В первом проекте отчета об EDVAC, подготовленном Джоном фон Нейманом в 1945 году,  уже упоминается задача сортировки. В то время такая задача представляла интерес как потенциальное нечисленное приложение ЭВМ. В 1948 году Нейман совместно с Германом Голдстайном (Herman Goldstine) опубликовал формальное описание алгоритма сортировки слиянием (Sorting based on meshing). 

Можно заметить, что сортировка обладает недостатком — расходами на дополнительную память. Однако, методы сортировки тесно переплетались с развитием ЭВМ. До появления EDVAC существовали эффективные специализированные сортировальные машины. В отчёте 1945 года EDVAC описывался как проект в разработке, а реализация алгоритма сортировки была ярким примером подхода, при котором компьютер может быть «универсальной» вычислительной машиной. Такой подход в дальнейшем станет известен как «архитектура фон Неймана».