Осциллирующая сортировка слиянием - Oscillating merge sort

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

Осциллирующая сортировка слияния "была разработана для лент, которые можно читать в обратном направлении, и в целом она более эффективна, чем многофазный или же каскад сливается ".^[1]

Рекомендации

1. Брэдли 1982, п. 190

• Брэдли, Джеймс (1982), Методы работы с файлами и базами данных, Холт, Райнхарт и Уинстон, ISBN  0-03-058673-9

дальнейшее чтение

• Флорес, Иван (1969), Компьютерная сортировка, Прентис-Холл, ISBN  978-0-13165746-5
• Кнут, Д. Э. (1975), Сортировка и поиск, Искусство программирования, 3, Эддисон Уэсли
• Лоуден, Б. Г. Т., «Заметка о колеблющемся роде» (PDF), Компьютерный журнал, 20 (1): 92, Дои:10.1093 / comjnl / 20.1.92
• Мартин, В. А. (1971), «Сортировка», Вычислительные опросы, ACM
• Собел, Шелдон (июль 1962 г.), "Осциллирующая сортировка - новый метод слияния сортировок", Журнал ACM, Нью-Йорк, Нью-Йорк: ACM, 9 (3): 372–374, Дои:10.1145/321127.321133

внешняя ссылка

• Михалдинец, Максимилиан (2016), "Вариант осциллирующей сортировки слиянием, реализованный в Matlab ", GitHub