The C++ sort algorithm is a core utility that arranges elements in a range according to a defined ordering. It is part of the Standard Library and offers powerful customization through predicates and iterator categories.
Programmers rely on this algorithm to bring order to containers such as vectors, lists, and arrays. Understanding its behavior, complexity guarantees, and usage patterns leads to more predictable and efficient code.
| Feature | Description | Complexity | Header |
|---|---|---|---|
| Default Ordering | Arranges elements in ascending order using | O(N log N) comparisons | <algorithm> |
| Custom Comparator | Allows user-defined ordering logic | O(N log N) comparisons | <algorithm> |
| Stable Variant | Preserves relative order of equivalent elements | O(N log N) comparisons | <algorithm> |
| Partial Sort | Sorts only the first N elements in order | O(N log N) comparisons | <algorithm> |
Default Behavior and Ordering Rules
Using operator
By default, std::sort arranges elements so that each element is less than or equal to the next. This behavior depends on the operator< or on a comparison object that satisfies the Compare requirement.
The comparator must define a strict weak ordering to produce a well-defined sequence. Violating this requirement leads to undefined behavior, so ensure transitivity and antisymmetry.
Iterator Categories and Performance
The algorithm adapts to random-access iterators, which are common for vectors and deques. With weaker iterator categories, the program may fail to compile, guiding you toward appropriate containers.
Custom Comparator Design Patterns
Pointers, References, and Function Objects
You can supply a lambda, a function pointer, or a function object to define ordering. Capture clauses are unnecessary for stateless comparators, keeping them lightweight and inlinable.
Sorting Complex Structures
To sort structs or classes, bind member pointers or extract fields inside the comparator. This approach keeps the data layout intact while controlling sort keys explicitly.
Performance Characteristics and Stability
Introsort and Complexity Guarantees
The standard mandates an average of O(N log N) comparisons. Implementations typically use introsort, which combines quicksort, heapsort, and insertion sort for optimal behavior on diverse inputs.
Stable Sort Alternatives
If equivalent elements must retain their original order, use std::stable_sort. It guarantees O(N log N) complexity while preserving sequence among equal values at a slight memory cost.
Best Practices and Recommendations
- Prefer
std::sortfor random-access containers requiring raw speed. - Choose
std::stable_sortwhen equal-key ordering must remain predictable. - Write comparators as const member functions or noexcept lambdas.
- Profile with realistic data to confirm that comparisons are not a bottleneck.
- Ensure strong exception safety by avoiding throwing operations inside predicates.
FAQ
Reader questions
Can I sort a vector of custom objects without modifying the class definition?
Yes, provide a comparator that accesses the relevant fields. A lambda with explicit parameters is ideal for scoping and avoiding global dependencies.
What happens when I use the wrong comparator signature?
The program may fail to compile or exhibit runtime errors. Ensure the comparator accepts const references and returns a bool that respects strict weak ordering.
Does std::sort allocate additional memory proportional to input size?
Typically it uses only a small constant amount of extra memory. Some implementations may allocate temporary buffers, but this does not scale linearly with container size.
Is it safe to sort containers while iterating over them?
Do not iterate with active iterators during a full sort, as their positions change. Collect indices or use indirect access if you need traversal during reordering.