Сортировка естественным неймановским слиянием :: Native Neumann Merge Sort

1. Всего используется три магнитные ленты - основная, на которой записаны неотсортированные данные и две вспомогательные.
2. Данные последовательно считываются с основной ленты.
3. Пока последовательно считываемые данные представляют из себя упорядоченный подмассив, они переписываются на одну из вспомогательных лент.
4. Как только завершается очередной отсортированный подмассив (т.е. на основной ленте встречается элемент, меньший чем предыдущий), на вспомогательной ленте ставится указатель (конец подмассива) и происходит переключение на другую вспомогательную ленту.
5. Пункты 2-4 повторяются снова, только данные переносятся уже на другую вспомогательную ленту. При завершении очередного упорядоченного подмассива на основной ленте происходит поочерёдное переключение то на одну вспомогательную ленту, то на другую.
6. Когда все данные с основной ленты считаны, происходит обработка вспомогательных лент.
7. С обеих вспомогательных лент поочерёдно считываются данные.
8. При этом очередные данные с двух лент сравниваются между собой. По результатами сравнения на основную ленту записывается меньший элемент из пары.
9. Так как границы массивов на вспомогательных лентах отмечены указателями, считывание и сравнение происходит только в пределах отсортированных подмассивов.
10. Если на одной из вспомогательных лент закончились элементы очередного подмассива, то с оставшейся ленты остаток подмассива просто переносится на основную ленту.
11. Повторяем весь процесс заново до тех пор, пока данные на основной ленте не будут собой представлять полностью упорядоченный массив.

Ссылки

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

Merge sort

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