Laboratory of Mathematical Logic at PDMI

Четверг, 12 июля, 203. Начало в 17:00.

Докладчик: А. Кноп.

Тема: Стабильные сортировки слиянием.

Abstract

Сортировка слиянием - это одна из самых популярных стабильных сортировок, она используется в большинстве стандартных библиотек на протяжении последних трех десятков лет. Однако сравнительно недавно Тим Питерс предложил модификацию этого алгоритма (Timsort) которая работает эффективнее на практике. Этот алгоритм стал стандартной сортировкой в Python и в Java. Однако с теоретической точки зрения его успех не был столь велик: первое доказательство того, что алгоритм сортирует n обьектов за O(n logn) операций было предложено лишь два года назад.

В докладе мы покажем что в худшем случае Timsort работает как минимум 1.5 n (log n + o(1)). Так же мы покажем оценки на ряд других алгоритмов устроенных подобно Timsort и предложим свой алгоритм (alpha-sort) которые работает эффективнее чем Timsort теоретичкски (гарантированное время работы alpha-sort меньше худшего времени работы Timsort) и в экспериментах.