spamsink | Программистское

Сегодня впервые прочитал о неизвестном мне ранее алгоритме сортировки smoothsort.
Этот алгоритм, разработанный Дейкстрой в 1981 году - вариант сортировки heapsort, отличающийся тем, что время его работы зависит от степени первоначальной отсортированности массива и плавно меняется от O(n) в лучшем случае до O(n log n) в худшем. Английская Википедия мягко замечает, что он используется редко из-за сложности алгоритма. Русская, впрочем, отмечает сложность в реализации как недостаток самого heapsort, а о smoothsort и не заикается.

Интересующимся предлагается ознакомиться с оригинальным текстом Дейкстры (16 страниц довольно слепого скана) или с HTML-транскрипцией - безотносительно к смысловой части алгоритма занимательно стилем изложения - или с реализациями: этой (С) или этими (C++, Delphi) и попробовать перевести на русский (или английский, FWIW) язык предложение "Trinkles the stretches when the adjacent stretches are already trusty."

Более сложного алгоритма сортировки мне не встречалось.