Сортировки слиянием

[saipr]

Сортировка слиянием. Как много напомнил этот заголовок. В далеком 1976 году я начинал службу в Прибалтике в г. Вентспилс . Из вычислительной техники у нас была ЭВМ М-220. А это 4К ОЗУ, 28К магнитный барабан и штук восемь лентопротяжек. Информации обрабатывалась немерино. Машинисток было много и они трудились без отдыха. И я только что закончивший Академию Ф.Э. Дзержинского, решил автоматизировать процесс формирования отчетов. За прототив был взят генератор отчетов от IBM — RPG. Так родился отечественный генератор (чем не импортозамещение) РПГ-М 220. За него я получил самую большую денежную премию 50 рублей. Что было примечательного?
Это сортировка информации, хранящейся на лентах. Сначала информация готовилась на перфокартах, затем она переносилась на ленту в ручную отсортированном порядке. За тем в лентопротяжки ставились три бабины: одна с новыми данными, вторая с данными, подготовленными ранее и чистая на которую переносилась информация получаемая слиянием.
Вы скажете какая древность. Но как были благодарны машинистки. К сожалению мы уже тогда начали отставать в развитии ЭВТ.
Спасибо автору. Есть что вспомнить.

[valemak]

Сортировка слиянием — это дизельпанк :)

[saipr]

А что сейчас ее не используют? В чем юмор-то?

[valemak]

Я имел ввиду, что первые алгоритмы сортировок этого класса придуманы именно под железо середины XX века. Чего, в принципе, не скажешь про другие классы сортировок.

Следующая статья будет посвящена кнуттовским сортировкам (многофазная, осциллирующая и каскадная сортировки слиянием), которые тоже лучше всего оценят те, кто не понаслышке знает про магнитные накопители и перфокарты.

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

[saipr]

Вот и хорошо.

[hdfan2]

Три бабины ставили бобины.

[saipr]

Да, сплоховал я: в горящую избу войдет. Да, бобины, бобины ...

[MisterN]

Сначала информация готовилась на перфокартах, затем она переносилась на ленту в ручную отсортированном порядке.

А зачем перфокарта, когда данные все-равно в ручном порядке на ленту переносятся? Я хлебушек, я ничего не понял.

[saipr]

В смысле, читались данные с перфокарты и записывались на ленту. Хлебушек, теперь понятно? По другому на ленту было не записать.

[MisterN]

Сложна было

[saipr]

Сложно? Да! Но интерессно

[dimitryvasya]

Статься классная, и анимации дают наглядное представление, но что с кодом? В функции bose_nelson_merge вместо

 if m = 1:
    if data[j] > if data[j + r]:

должно быть

 if m == 1:
    if data[j] > data[j + r]:

И после объявления функций не хватает двоеточий.

[valemak]

Благодарю за замечания, когда уже Вашим комментариям не будет требоваться модерация — просьба о подобных огрехах писать авторам в личку.

Статью писал ночью, утром уже не было никаких сил вычитать код.

[ov7a]

Наверно, в статью стоит добавить сложность второго алгоритма.

[MisterN]

А насчет Манхеттенского проекта, он внес что-нибудь в развитие ЭВМ и как вообще вычислительная техника в нем использовалась? Что-то про Оппенгеймера вроде полно инфы, а про фон Неймана в Манхеттенском и главное про компьютеры, которые в проекте использовались, не особенно.