Неудовлетворенный
<a href="https://xkcd.com/584/" target="_blank"><img src="https://xkcd.ru/i/584_v1.png" border="0" alt="Неудовлетворенный"></a>
<p>
Вечно все сравнивают, но никогда не оценивают хоть по какой-нибудь внешней шкале. Если бы вы были сортирующей функцией, вы бы ни за что не преодолели барьер в O(NlogN).
<p><lj-cut text="дополнительная информация">
<hr size=1 width="80%">
<p>
Любой алгоритм сортировки, <a href="http://en.wikipedia.org/wiki/Comparison_sort">основанный на сравнениях</a>, не может в худшем случае выполниться быстрее, чем за время, пропорциональное NlogN от размера входных данных.
</lj-cut>
Вечно все сравнивают, но никогда не оценивают хоть по какой-нибудь внешней шкале. Если бы вы были сортирующей функцией, вы бы ни за что не преодолели барьер в O(NlogN).
Любой алгоритм сортировки, основанный на сравнениях, не может в худшем случае выполниться быстрее, чем за время, пропорциональное NlogN от размера входных данных.