Естественная сортировка слиянием с минимизацией объема дополнительной памяти

• Published in: Электронное моделирование
• Date: 2011
• Main Author: Винничук, С.Д.
• Format: Article
• Language: Russian
• Published: Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України 2011
• Subjects: Вычислительные процессы и системы
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/61791
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Естественная сортировка слиянием с минимизацией объема дополнительной памяти / С.Д. Винничук // Электронное моделирование. — 2011 — Т. 33, № 6. — С. 33-56. — Бібліогр.: 3 назв. — рос.

Предложен алгоритм, требующий объема дополнительной памяти O (logn), с трудоемкостью в худшем случае O (nlog2 n). Предложены также алгоритмы устойчивой нерекурсивной сортировки слиянием, позволяющие учитывать естественную упорядоченность исходного массива данных длиной n при уменьшении объема дополнительной памяти до величин n/2 + O (1), n/4 + O (1), n/8 + O (1) и трудоемкости в случае наихудшего расположения элементов порядка O (nlogn). Запропоновано алгоритм, що потребує обсягу додаткової пам’яті O (logn), з трудомісткістю для гіршого випадку O (nlog2 n). Запропоновано також стійкі нерекурсивні алгоритми сортування злиттям, які дозволяють враховувати природню впорядкованість початкового масиву даних довжиною n при зменшенні обсягу додаткової пам’яті до величин n/2 + O (1), n/4 + O (1), n/8 + O (1) з трудомісткістю для гіршого випадку O (nlogn). An algorithm has been proposed, which requires additional memory of the order O (logn) with an estimate of the labour input in the worst case of order O (nlog2n). Variants of resistant nonrecursive merge sorting algorithms have been proposed that take into account the natural ordering of the original data array of length n, with a decrease in the volume of additional memory to the values of n/2 + O (1), n/4 + O (1), n/8 + O (1), and labour input in the worst case of elements location of the order O (nlogn).