Осциллирующая сортировка слиянием
Осциллирующая сортировка слиянием или осциллирующая сортировка — это вариант сортировки слиянием, используемый с ленточными накопителями, которые могут читать в обратном направлении. Вместо полного распределения, как это делается при слиянии ленты, распределение входных данных и объединение прогонов чередуются. Осциллирующая сортировка слиянием не тратит время на перемотку и не приводит к простою ленточных накопителей, как при обычном слиянии лент.
Осциллирующая сортировка слиянием «была разработана для лент, которые можно читать в обратном направлении, и в целом она более эффективна, чем многофазное или каскадное слияние». [1]
Ссылки
[ редактировать ]- ^ Брэдли 1982 , с. 190
- Брэдли, Джеймс (1982), Методы работы с файлами и базами данных , Холт, Райнхарт и Уинстон, ISBN 0-03-058673-9
Дальнейшее чтение
[ редактировать ]- Флорес, Иван (1969), Компьютерная сортировка , Прентис-Холл, ISBN 978-0-13165746-5
- Кнут, Д.Э. (1975), Сортировка и поиск , Искусство компьютерного программирования , вып. 3, Эддисон Уэсли
- Лоуден, БГТ, «Заметка об осциллирующей сортировке» (PDF) , The Computer Journal , 20 (1): 92, doi : 10.1093/comjnl/20.1.92 [ мертвая ссылка ]
- Мартин, Вашингтон (1971), «Сортировка», Computing Surveys , 3 (4), ACM: 147–174, doi : 10.1145/356593.356594
- Собел, Шелдон (июль 1962 г.), «Осциллирующая сортировка – новая техника слияния сортировок», Journal of the ACM , 9 (3), Нью-Йорк, Нью-Йорк: ACM: 372–374, doi : 10.1145/321127.321133 , S2CID 11554742
Внешние ссылки
[ редактировать ]- Михалдинец, Максимилиан (2016), « Вариант сортировки осциллирующим слиянием, реализованный в Matlab », GitHub