sort(), sort_heap(), stable_sort() STL, PureCodeCpp

Сортировките съставляват напълно специална група алгоритми - на практика трябва да сортирате голямо разнообразие от обекти и според голямо разнообразие от критерии. Анализът на алгоритмите за сортиране е добре и задълбочено проучен, както никой друг клон на изчислителната математика. Основният проблем на всеки алгоритъм за сортиране е неговата изчислителна сложност - броят на операциите за сравняване и обмен, необходими за сортиране на последователност с дължина N, т.нар. O(N).

Неприятно обстоятелство е, че за различните алгоритми средната сложност (на повечето тестови последователности) и максималната сложност (на най-лошата тестова последователност за метода) се различават. За няколко десетки сортиращи алгоритми, предлагани в процеса на обучение по програмиране, е показано, че по-голямата част от тях (интуитивно разбираеми) са най-лошите по отношение както на средна, така и на максимална сложност. Като пример, популярният тип балон сред студентите е най-лошият от всички известни.

Само няколко метода за бързо рекурсивно сортиране са ефективни (по отношение на сложността) от целия набор от методи. Те са представени и в имплементациите на STL алгоритми. Стандартите не настояват за твърдо ограничение на вътрешните механизми на тяхното прилагане, така че може да има опции в зависимост от използваната библиотека.

Сега, след като имаме известни познания за алгоритмите, функторите и общото състояние на нещата със сортирането, ние сме готови да разгледаме опциите за прилагане на всичко това в нашия код. Като начало сортираме числовите последователности по различни начини. Примерът е твърде голям, но е предназначен не само и не толкова за илюстрация, колкото за последващо самостоятелноекспериментиране:

---