В общем — не так уж и плоха. Но автор писал об этом всём в контексте геймдева, где дорога каждая микросекунда, поскольку надо выдать много fps и в хорошем качестве. Интерфейс, базовый класс и реализация приведут к тому, что в объекте будет создана таблица виртуальных функций, а каждый вызов функции приведёт к поиску в этой таблице адреса, по которому её нужно вызывать. Это всё затраты времени. Копеечные в обычном приложении, но существенные в игре. Вариант с шаблонами позволяет этого избежать.
Ок, а что на счёт батареек на спирту? Пришел в офис\домой, прицепил телефончик к станционарному бутлю, налил грамм 50 — и день аппарат живет. Быстро, удобно + еще и экологично может быть. Не?
Никто и не спорит, что другие алгоритмы имеют право на жизнь, статья описывает только достоинства и недостатки данного алгоритма. А что и когда использовать — решать нужно в каждом конкретном случае. «Стабильность», к стати, означает еще и то, что если в сортируемом массиве встретятся подряд идущие одинаковые элементы — стабильный метод их переставлять не будет, а нестабильный волен хоть 100 раз их перетасовать.
Я так думаю, что лучшее применение этой штуки — например, слить в одну пару таблиц из базы или листов из экселевской книги. Частично отсортированные данные, величины порядка тысяч\миллионов записей — самое то.
Вы знаете, серьёзных фундаментальных исследований на эту тему по Timsort я нигде не встречал. В оригинальной статье (ссылка в конце статьи) автор алгоритма сравнивает Timsort с samplesort, quicksort и mergesort и показывает (в основном, по факту тестов, а не теоретически) преимущество Timsort над ними в пределах от 1.5% скорости до вообще нереальных чисел.
Если Вы об использовании памяти, то Timsort в самом худшем случае требует 0.5*N памяти. Если о лучшем случае — то коэфициент чётко 1 (т.е. нужно будет ровно N операций сравнения).
Это не перевод. Это компиляция примерно десятка статей, с собственными примерами и пояснениями. Собственно говоря, ни одного предложения просто «в лоб» переведённого в статье нет.
Табличка просто взята с Википедии ввиду того, что таблички размером побольше нигде найдено не было. Ясное дело, что алгоритмов намного больше, и понятно, что Timsort не «предел мечтаний». Просто у него тоже есть своя ниша, а статья — всего лишь его описание.
При уже отсортированном массиве — ничем не лучше. Даже обычной сортировки вставской не лучше. Лучше на массиве, содержащем, скажем, 20 упорядоченных подмассивов, которые, однако, не упорядочены между собой.
Т.е. проще говоря, идеальные случаи отличаются и, по мнению автора, хорошие для Timsort случаи встречается в реальной жизни чаще хороших случаев других алгоритмов.
Я так думаю, что лучшее применение этой штуки — например, слить в одну пару таблиц из базы или листов из экселевской книги. Частично отсортированные данные, величины порядка тысяч\миллионов записей — самое то.
Т.е. проще говоря, идеальные случаи отличаются и, по мнению автора, хорошие для Timsort случаи встречается в реальной жизни чаще хороших случаев других алгоритмов.