Сортировки: сравнение алгоритмов, std::sort изнутри

Введение

Сортировка — одна из самых частых операций в практическом коде, и std::sort/std::ranges::sort обычно используются как готовый, не требующий раздумий инструмент — в этой статье разберём, что происходит «под капотом», и сравним основные классы алгоритмов сортировки по их сложности и практическим компромиссам.

Концепция

Простые алгоритмы (сортировка пузырьком, сортировка вставками) имеют сложность O(n²) в общем случае, что приемлемо для очень маленьких коллекций, но непрактично для больших. Эффективные алгоритмы общего назначения (быстрая сортировка/quicksort, сортировка слиянием/merge sort, пирамидальная сортировка/heapsort) достигают O(n log n) — std::sort обычно реализован как гибридный алгоритм (introsort), начинающий с quicksort (быстрого в среднем случае, но с O(n²) худшим случаем для неудачно подобранных данных), переключающийся на heapsort при обнаружении признаков приближения к этому худшему случаю (гарантируя O(n log n) даже в худшем случае), и завершающий сортировку очень маленьких подмассивов через сортировку вставками (эффективную именно для малых n, несмотря на формально худшую асимптотику). Стабильная сортировка (std::stable_sort) дополнительно гарантирует сохранение исходного относительного порядка для элементов, считающихся равными при сравнении, что важно, когда порядок равных элементов имеет значение (например, при сортировке по одному полю с сохранением исходного порядка для одинаковых значений этого поля).

Пример кода

// std::sort — типичное использование с пользовательским компаратором
#include <algorithm>

struct Order { QString customerName; double amount; };
std::vector<Order> orders = { /* ... */ };

std::sort(orders.begin(), orders.end(), [](const Order &a, const Order &b) {
    return a.amount > b.amount; // по убыванию суммы заказа
});

// std::stable_sort — важно, когда порядок равных элементов значим
std::vector<Order> ordersByDate; // предположим, изначально уже отсортированы по дате создания
std::stable_sort(ordersByDate.begin(), ordersByDate.end(), [](const Order &a, const Order &b) {
    return a.customerName < b.customerName;
});
// Заказы ОДНОГО клиента после stable_sort останутся в исходном порядке по дате —
// обычный std::sort такой гарантии не даёт, относительный порядок равных элементов не определён

// Демонстрация худшего случая quicksort (концептуально) — почему introsort переключается на heapsort
// Наивный quicksort с выбором первого элемента как опорного (pivot) деградирует до O(n²)
// на уже отсортированных или специально сконструированных враждебных данных:
std::vector<int> alreadySorted(100000);
std::iota(alreadySorted.begin(), alreadySorted.end(), 0); // 0, 1, 2, ..., 99999
// Наивный quicksort на таких данных с плохим выбором pivot выполнил бы O(n²) операций —
// std::sort избегает этой проблемы через introsort-гибрид с гарантированным переключением на heapsort

Пояснения к коду

Сортировка orders через лямбда-компаратор показывает идиоматичное, гибкое использование std::sort — критерий сортировки выражается произвольной логикой сравнения, а не ограничен встроенными типами или единственным «естественным» порядком. Разница между std::sort и std::stable_sort на примере ordersByDate показывает практически значимое различие — после сортировки по имени клиента сохранение исходного относительного порядка по дате для заказов одного клиента важно для предсказуемого, ожидаемого пользователем поведения (заказы каждого клиента видны в хронологическом порядке), что не гарантировано обычным std::sort, для которого относительный порядок равных по компаратору элементов формально не определён. Демонстрация худшего случая quicksort на уже отсортированных данных объясняет, почему std::sort современных реализаций — не «чистый» quicksort, а гибридный introsort, специально спроектированный для избежания именно такого катастрофического вырождения производительности на неудачно подобранных входных данных.

Подводные камни

• Использование std::sort вместо std::stable_sort, когда относительный порядок равных элементов реально важен для корректности или ожидаемого поведения приложения — это легко пропустить, поскольку оба варианта в большинстве случаев дают визуально похожий, «разумный» результат, и проблема (нарушенный порядок равных элементов) может остаться незамеченной до специфичного тестового случая или жалобы пользователя на «странное», непредсказуемое поведение сортировки.
• Реализация собственного алгоритма сортировки вместо использования std::sort без действительно веской причины (специфичные требования, не покрываемые стандартной библиотекой) — стандартная реализация std::sort тщательно оптимизирована, протестирована и устойчива к худшим случаям через introsort-гибрид, и самостоятельная реализация классического алгоритма сортировки (например, наивного quicksort) рискует воспроизвести именно те проблемы (худший случай O(n²)), которые стандартная библиотека уже решила.
• Игнорирование стоимости копирования объектов при сортировке коллекции сложных, «тяжёлых» объектов по значению — если элементы коллекции дорого копировать (большие объекты, не оптимизированные через move-семантику), сортировка может стать заметно медленнее из-за множества операций копирования/перемещения, выполняемых алгоритмом сортировки; для таких случаев стоит рассмотреть сортировку индексов или указателей на объекты вместо самих объектов, либо обеспечить эффективную move-семантику для типа элемента.
• Сортировка по сложному, дорогому в вычислении критерию без кеширования промежуточного результата вычисления этого критерия — если компаратор каждый раз пересчитывает дорогое значение (например, сложную агрегацию) для сравнения, а не использует заранее вычисленное и сохранённое значение, общая стоимость сортировки может оказаться значительно выше из-за многократного, избыточного пересчёта одного и того же значения для одного и того же элемента при разных сравнениях в ходе работы алгоритма сортировки.