C++ Sorting: std::sort, stable_sort, partial_sort and nth_element

By 0xmote · May 27, 2026 · 13 min read · Updated Sep 25, 2026 Intermediate tutorial

Key takeaways

Compare C++ std::sort, stable_sort, partial_sort, and nth_element: custom comparators, partial sorts, median selection, and practical STL sorting patterns.

What are sorting algorithms?

Sorting algorithms in the STL rearrange elements into a given order. C++ provides several sorting variants optimized for different use cases.

The C++ Standard Library sorting algorithms are highly optimized implementations that often outperform hand-written sorting code. They use sophisticated techniques like introsort (a hybrid of quicksort, heapsort, and insertion sort) to guarantee good performance across all input patterns.

#include <algorithm>
#include <vector>
std::vector<int> v = {3, 1, 4, 1, 5};
std::sort(v.begin(), v.end());
std::sort(v.begin(), v.end(), std::greater<>());

Why use them?

Organize data in a defined order
Enable binary search on sorted ranges
Performance from tuned implementations
Flexibility via custom comparators Kinds of sorting algorithms: | Algorithm | Time | Stable | Typical use | |-----------|------|--------|-------------| | sort | O(n log n) | No | General-purpose sort | | stable_sort | O(n log n) ~ O(n log² n) | Yes | Preserve input order for ties | | partial_sort | O(n log k) | No | Top k only | | nth_element | O(n) average | No | Median or k-th order statistic |

Stability: stable_sort keeps relative order for equal keys; sort does not guarantee it.

Performance considerations: Choose the right algorithm based on your needs. If you only need the top 10 elements from 1 million items, partial_sort is dramatically faster than sorting everything. For finding medians or percentiles, nth_element is your best choice.

sort

#include <algorithm>
std::vector<int> v = {3, 1, 4, 1, 5};
std::sort(v.begin(), v.end());
std::sort(v.begin(), v.end(), [](int a, int b) {
    return a > b;
});

Since C++11 the standard requires std::sort to perform O(n log n) comparisons in the worst case, not just on average. That guarantee is why every major library uses introsort: a quicksort that watches its recursion depth and switches to heapsort once the depth exceeds about 2·log₂ n, then finishes small partitions with insertion sort. You do not get the classic quicksort blow-up on already-sorted or adversarial input.

What std::sort requires from you is random-access iterators and move-assignable, swappable elements. That rules out std::list and std::forward_list (use their .sort() member, which is a stable merge sort) and it means sorting a vector of large objects moves them around a lot. When the objects are expensive to move, sorting a vector of indices or pointers and then applying the permutation is often faster.

std::greater<>() (the transparent form with empty angle brackets, C++14) is preferable to std::greater<int>() because it deduces the argument types and avoids accidental conversions when the element type later changes to long long or double.

Sorting Structs, stable_sort, partial_sort, and nth_element

Real-world sorting often involves custom data types and complex sorting criteria. Understanding how to write effective comparators is crucial for leveraging C++‘s sorting algorithms.

Sorting structs

When sorting custom objects, you need to define comparison logic. The comparator must implement a strict weak ordering - it should be asymmetric, transitive, and irreflexive. Violating these rules leads to undefined behavior.

#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
struct Person {
    std::string name;
    int age;
};
int main() {
    std::vector<Person> people = {
        {"Charlie", 35},
        {"Alice", 25},
        {"Bob", 30}
    };
    
    std::sort(people.begin(), people.end(), 
        [](const Person& a, const Person& b) {
            return a.age < b.age;
        });
    
    for (const auto& p : people) {
        std::cout << p.name << " (" << p.age << ")" << std::endl;
    }
}

The lambda takes const Person& so each comparison does not copy a std::string; a by-value comparator compiles and gives the same order, but it copies two strings on every one of the roughly n log n comparisons. When you need a tie-breaker (same age, sort by name), compare std::tie(a.age, a.name) < std::tie(b.age, b.name) instead of hand-writing nested ifs — std::tuple’s operator< is lexicographic and satisfies strict weak ordering by construction.

stable_sort

With std::sort, Alice and Charlie (both 85) may come out in either order, and the order can change between compilers or even between input sizes. stable_sort guarantees Bob before David and Alice before Charlie, because that is how they appeared in the input. The classic use is multi-pass sorting: sort by the secondary key first, then stable_sort by the primary key, and the secondary order survives inside each group — the same trick spreadsheets use when you click one column header after another.

#include <algorithm>
struct Student {
    std::string name;
    int score;
};
int main() {
    std::vector<Student> students = {
        {"Alice", 85},
        {"Bob", 90},
        {"Charlie", 85},
        {"David", 90}
    };
    
    std::stable_sort(students.begin(), students.end(),
        [](const Student& a, const Student& b) {
            return a.score > b.score;
        });
    
    for (const auto& s : students) {
        std::cout << s.name << ": " << s.score << std::endl;
    }
}

partial_sort

#include <algorithm>
int main() {
    std::vector<int> v = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    
    std::partial_sort(v.begin(), v.begin() + 3, v.end());
    
    std::cout << "Top 3: ";
    for (int i = 0; i < 3; ++i) {
        std::cout << v[i] << " ";
    }
}

After the call, v[0..3) holds 0 1 2 in sorted order, and the remaining seven elements are in unspecified order — do not rely on them being untouched or sorted. partial_sort works by building a heap of the first k elements and sifting the rest through it, which is why the cost is O(n log k): for k = 10 out of a million elements it does far less work than a full sort. As k approaches n, though, the heap approach becomes slower than plain std::sort, so it only pays off when k is small relative to n. If you need the top k in a separate container without touching the source, std::partial_sort_copy does that.

nth_element

nth_element is a selection algorithm (typically introselect). After the call, the element at mid is the one that would be there if the whole range were sorted, everything before it is not greater, and everything after it is not less — but neither side is sorted. That is exactly enough for a median, a percentile, or a “split into top half and bottom half” step, at O(n) average cost.

For an even-sized range this code returns the upper median. If you need the mean of the two middle values, call nth_element for mid, then take *std::max_element(v.begin(), v.begin() + mid) for the lower one — the left side already contains only smaller-or-equal values, so no second full selection is needed.

#include <algorithm>
int main() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    
    size_t mid = v.size() / 2;
    std::nth_element(v.begin(), v.begin() + mid, v.end());
    
    std::cout << "Median: " << v[mid] << std::endl;
}

Which Sort Variant to Use

std::sort(v.begin(), v.end());
std::stable_sort(v.begin(), v.end());
std::partial_sort(v.begin(), v.begin() + n, v.end());
std::nth_element(v.begin(), v.begin() + n, v.end());
bool sorted = std::is_sorted(v.begin(), v.end());

Stability, Comparator, and Range Pitfalls

Stability

Use stable_sort when equal keys must keep their original relative order.

Comparator must be a strict weak ordering

// Wrong: comp(a, a) returns true, which violates strict weak ordering
std::sort(v.begin(), v.end(), [](int a, int b) {
    return a <= b;
});
// Right
std::sort(v.begin(), v.end(), [](int a, int b) {
    return a < b;
});

The <= version is undefined behavior, and the failure mode is nasty. The partition step in libstdc++‘s introsort uses an unguarded inner loop that relies on the comparator returning false when an element is compared with the pivot’s equal. With <=, that loop can run past the end of the range when many elements are equal, and you get a segfault or corrupted heap — often only with production-sized data, never with the ten-element unit test. I have seen this exact bug show up as a crash inside std::__unguarded_partition in a stack trace, which looks like a library bug until you look at the lambda. MSVC debug builds catch it earlier with an “invalid comparator” assertion, and -D_GLIBCXX_DEBUG on GCC does the same.

A subtler variant is a comparator that is not transitive, such as comparing floating-point values where some are NaN (every comparison with NaN is false, so NaN is “equal” to everything and transitivity of equivalence breaks). Filter out or explicitly order NaNs before sorting.

Performance characteristics

sort — O(n log n) (worst case, since C++11); stable_sort — O(n log n) when it can allocate a temporary buffer, O(n log² n) when it cannot; partial_sort — O(n log k); nth_element — O(n) average.

The stable_sort range matters in memory-constrained code: it tries to allocate a buffer of up to n elements, and if that allocation fails it silently falls back to an in-place merge that is noticeably slower. It does not throw — it just gets slower.

Iterator ranges

std::sort(v.end(), v.begin()) is undefined — keep first <= last.

One-Line Calls for Each Variant

std::sort(v.begin(), v.end());
std::sort(v.begin(), v.end(), std::greater<>());
std::stable_sort(v.begin(), v.end());
std::partial_sort(v.begin(), v.begin() + k, v.end());
std::nth_element(v.begin(), v.begin() + mid, v.end());

Multi-Key Sorts, Top-K, and Banded Sorts

Three patterns cover most real code:

Multi-key sort (department ascending, then salary descending): one std::sort with a lambda that compares a.dept != b.dept ? a.dept < b.dept : a.salary > b.salary. Mixing ascending and descending keys is where std::tie gets awkward; negating a numeric key inside the tuple works for integers but not for strings, so the explicit ternary is clearer.
Top-K: partial_sort when you need the k items in order (a leaderboard), nth_element when you only need the set of k items (the 100 largest files to delete), which is cheaper.
Banded sort (priority bucket, then deadline): if priorities are a small enum, std::stable_partition or a counting approach per bucket followed by sorting each bucket by deadline is often simpler to reason about than one large comparator.

One more production habit: when a comparator reads a field that is expensive to compute (a string’s lowercase form, a distance), precompute it once into a vector of (key, index) pairs and sort that. Computing the key inside the comparator repeats the work about 2·n log n times.

FAQ

Q1: What is `sort`?

A: A fast sort with O(n log n) comparisons, guaranteed in the worst case since C++11; not stable.

Q2: What is `stable_sort`?

A: A stable sort: equal keys keep their original order.

Q3: What is `partial_sort`?

A: Sorts only the first k elements; O(n log k).

Q4: How do I write a comparator?

A: It must satisfy strict weak ordering. Use <.

Q5: Why does my sort crash only on large inputs?

A: Almost always an invalid comparator (<=, or NaN values). See the strict weak ordering pitfall above; build with -D_GLIBCXX_DEBUG or an MSVC debug build to get an “invalid comparator” diagnosis instead of a crash.

Q6: How do I verify sorted order?

A: Use std::is_sorted.

Q7: Custom types?

A: Define operator< or pass a comparison function.

Q8: Further reading?

A: Effective STL (Items 31–34), C++ Primer, cppreference — sort. One-line summary: C++ STL sorting offers efficient options for full sort, stability, partial sort, and order statistics.