The STL's sorting family covers four jobs: sort the whole range, sort while preserving the order of equal elements, sort only the first k smallest, and partition around the element that belongs at position n. Each one has different complexity guarantees and different trade-offs, and the right pick depends on what is needed from the result. This chapter walks through std::sort, std::stable_sort, std::partial_sort, and std::nth_element, plus the comparator rules they all share.

std::sort(first, last) sorts the range in ascending order using the default operator< for the element type. It is the algorithm to use unless there is a specific reason not to.

The standard guarantees O(n log n) on average and in the worst case, and that the sort happens in place (no extra heap allocation beyond what the comparator itself might do). It does not guarantee stability, which matters when there are equal keys; covered next.

Most implementations use introsort, a hybrid algorithm invented by David Musser in 1997. Introsort starts with quicksort because quicksort is fast in practice. If the recursion depth grows past about 2 * log2(n), suggesting quicksort has hit a pathological input that is heading toward O(n²), the implementation switches to heapsort, which guarantees O(n log n) in the worst case. For small sub-ranges (typically under 16 elements), it switches to insertion sort, which is cache-friendly and beats both at that scale.

The user-facing contract is "O(n log n) worst case and average." The introsort detail is how implementations meet that contract; it is not necessary during normal use, but it explains why std::sort handles adversarial inputs that would trip up a naive quicksort.

Before C++11, std::sort only guaranteed average O(n log n), with no worst-case bound. The C++11 standard strengthened the guarantee, which is why introsort is the universal choice today.

std::sort is O(n log n) and in-place (O(log n) auxiliary space from recursion). Sorting a vector of 1 million ints typically takes a few tens of milliseconds on modern hardware; sorting a vector of 1 million std::string values is much slower because each comparison touches heap memory.

A sort is stable if elements with equal keys keep their relative order from the input. std::sort is not stable. If two elements compare equal under the comparator, the algorithm is free to swap them or not, and the order is unpredictable.

For sorting prices or simple keys, this does not matter; equal is equal. It matters when the elements carry data the comparator does not look at, and the order of equal-keyed elements matters.

A possible output is:

ORD-B came before ORD-D in the input, but std::sort placed ORD-D first in the result. Both have priority 1, the comparator sees them as equal, and the algorithm reshuffled them. On a different compiler or with a different vector size, the order of the equal-priority orders might be different. If the relative input order matters, use a stable sort.

std::stable_sort does the same job as std::sort but preserves the relative order of equal elements.

ORD-B came before ORD-D in the input, and both come out in the same relative order. Same for the priority-2 group: ORD-A, ORD-C, ORD-E keep their original ordering.

Stability is not free. std::stable_sort typically uses merge sort, which allocates an auxiliary buffer to hold a copy of the range during merging. If the allocation succeeds, the complexity is O(n log n) in the worst case. If the allocation fails (the system is out of memory or the requested buffer is too large), it falls back to an in-place merge sort with O(n log² n) worst case. The standard explicitly allows this two-tier guarantee.

Use std::stable_sort only when order of equal keys matters. The auxiliary allocation is a real cost on memory-constrained systems, and the constant factor is larger than std::sort's.

A comparator is anything callable as comp(a, b) that returns true if a should appear before b. The default comparator is std::less<T>, which calls operator<. Any callable works: a free function, a function object, or a lambda.

Switch the lambda to a.price < b.price for ascending. The comparator returns "does a come before b?" so flipping the direction is the same as flipping the operator.

The same idea works for sorting by member or computed key. Sort customers by the last four characters of their email, by total spent, by length of name, or any other key.

For an even cleaner approach when sorting by member, C++20 ranges introduce projections, which let you write std::ranges::sort(customers, std::greater{}, &Customer::lifetimeSpend). The Ranges chapter covers it.

Strict Weak Ordering

The comparator must define a strict weak ordering, which is a fancy way of saying it has to be consistent. Three concrete rules:

If the comparator breaks any of these, the behaviour of std::sort is undefined. The program might crash, loop forever, produce garbage, or appear to work and corrupt data hours later. This is a real source of production bugs, especially with floating-point keys where NaN breaks reflexivity (NaN < NaN is false, but comp(a, b) where both are NaN should also be false, and the algorithm may still misbehave around NaN values).

The fix is < instead of <=. The comparator must treat equal elements as incomparable, not "either order is fine." Phrased differently: if comp(a, b) is false and comp(b, a) is also false, the algorithm concludes that a and b are equivalent.

A bad comparator is undefined behaviour, not a graceful error. Stress-test custom comparators on random inputs that include duplicates. Modern implementations of std::sort may detect some bad comparators in debug builds, but this cannot be relied on.

Sometimes the whole range does not need to be sorted. The top 10 best-selling products out of 10,000, or the 5 most recent orders out of millions, only need partial sorting. std::sort would do the job and waste time on the elements that do not matter. std::partial_sort fits.

std::partial_sort(first, middle, last) rearranges the range so that the smallest middle - first elements end up in [first, middle) in sorted order. The remaining elements in [middle, last) are unspecified.

The first three elements are the three smallest values in sorted order. The remaining seven elements are in some unspecified order. The whole range is not sorted.

std::partial_sort runs in O(n log k) where k = middle - first. For k much smaller than n, that's a meaningful win over a full sort.

Internally, most implementations use a heap-based approach: build a max-heap of size k from the first k elements, then for every remaining element, compare against the heap's top and replace it if smaller. At the end, sort the heap in place.

std::nth_element(first, nth, last) does something subtler. It rearranges the range so that the element that would be at position nth if the range were fully sorted is actually there. Everything before nth is less than or equal to that element, and everything after is greater than or equal. Neither half is sorted.

A possible output is:

23 is the value that would sit at index 4 in a fully sorted range. Everything before it (18 12 4 7) is less than or equal to 23. Everything after (56 33 99 45 89) is greater than or equal. Neither side is sorted internally.

The complexity is O(n) on average, which is faster than even partial_sort. The implementation is typically based on quickselect, a partition-based algorithm that recursively narrows in on the target position. Worst-case complexity is O(n²) for naive implementations, but modern standard libraries use a variant (introselect) that guarantees O(n) on average and O(n log n) worst case.

Why does nth_element exist? Three common reasons:

The third pattern is the one to remember. It's the standard "top-K reviews" or "top-K best-sellers" pipeline.

For 10 products this is overkill, but the pattern scales: 10 million products would still find the top 3 in roughly 10 million comparisons rather than ~233 million for a full sort.

Before sorting, it's sometimes worth asking whether the range is already sorted. After sorting, asserting that the result is sorted catches bugs in custom comparators.

std::is_sorted(first, last) returns true if the range is sorted under the default operator< (or a comparator you provide). std::is_sorted_until(first, last) returns an iterator to the first element that violates sorted order, or last if the range is fully sorted.

Both run in O(n) and short-circuit on the first violation. They accept a custom comparator with the same strict-weak-ordering rules; pass it the same way you'd pass one to sort.

A common use is in test code: sort the data, then assert sortedness before checking other properties. If the assertion fails, you know the comparator is broken before chasing downstream bugs.

std::sort, std::stable_sort, std::partial_sort, and std::nth_element all require random-access iterators. They need to jump by arbitrary offsets, swap arbitrary elements, and re-partition the range, all of which assume O(1) iterator arithmetic.

std::vector, std::deque, and built-in arrays all offer random-access iterators. std::list and std::forward_list don't; their iterators are bidirectional and forward respectively. Calling std::sort(list.begin(), list.end()) doesn't compile.

With g++ this fails with a message like error: no match for 'operator-' (operand types are 'std::_List_iterator<int>' and 'std::_List_iterator<int>'). The error comes from std::sort trying to compute distances, which a list iterator can't do.

std::list provides its own member function nums.sort() that uses merge sort internally and works on bidirectional iterators. That sort is stable and runs in O(n log n). The Iterator Categories chapter covers why containers like list need their own member sort.

The rule of thumb: if a container offers random-access iterators, prefer the STL sort algorithms; if not, look for a member sort first.

Once you know all four, the decision tree is short.

Said as prose:

Building on that quick-check insight: when you need to sort by multiple keys, the cleanest approach is a single comparator that captures the full ordering, not a chain of sorts.

The comparator returns the primary-key comparison when the keys differ, and falls through to the secondary key when they match. The same pattern extends to three or more keys with one if per level. Since C++20 you can replace the body with a single return std::tie(a.customer, a.date) < std::tie(b.customer, b.date); using lexicographic tuple comparison, which is even shorter.

This single-comparator approach is usually preferable to chained sorts because it's clearer at the call site, doesn't depend on stability, and is one pass through the data instead of N passes.