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

• Veröffentlicht in: Электронное моделирование
• Datum: 2011
• 1. Verfasser: Винничук, С.Д.
• Format: Artikel
• Sprache: Russian
• Veröffentlicht: Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України 2011
• Schlagworte: Вычислительные процессы и системы
• Online Zugang: https://nasplib.isofts.kiev.ua/handle/123456789/61791
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Zitieren: Естественная сортировка слиянием с минимизацией объема дополнительной памяти / С.Д. Винничук // Электронное моделирование. — 2011 — Т. 33, № 6. — С. 33-56. — Бібліогр.: 3 назв. — рос.

Предложен алгоритм, требующий объема дополнительной памяти O (logn), с трудоемкостью в худшем случае O (nlog2 n). Предложены также алгоритмы устойчивой нерекурсивной сортировки слиянием, позволяющие учитывать естественную упорядоченность исходного массива данных длиной n при уменьшении объема дополн...