Library

since C++98

Basic

Sorting Algorithms

"C++ sorting: std::sort, std::stable_sort, std::partial_sort, std::nth_element, ranges variants, custom comparators, and strict weak ordering."

Sorting Algorithmssince C++98

The <algorithm> sorting family provides std::sort (introsort, O(n log n), unstable), std::stable_sort (mergesort, preserves equal-element order), std::partial_sort (sorted top-k in O(n log k)), and std::nth_element (O(n) linear partition) — all requiring random-access iterators, with C++20 ranges variants adding projection support.

Overview

C++ provides four sorting primitives with distinct complexity and stability trade-offs. All accept an optional comparator satisfying strict weak ordering; C++20 ranges variants additionally accept a projection applied to each element before comparison.

Iterator requirements are non-negotiable. std::sort, std::partial_sort, and std::nth_element require random-access iterators. They cannot be applied to std::list or std::forward_list — those containers expose sort() member functions instead.

cpp

std::list<int> lst{5, 3, 8, 1};
// std::sort(lst.begin(), lst.end()); // compile error — bidirectional only
lst.sort();                           // member mergesort, O(n log n), since C++98
lst.sort(std::greater<int>{});

std::forward_list::sort() was added in C++11. Both member sorts preserve iterator and pointer validity, which a sort-via-copy-to-vector approach cannot.

Syntax

cpp

// Since C++98
template<class RandomIt>
void sort(RandomIt first, RandomIt last);

template<class RandomIt, class Compare>
void sort(RandomIt first, RandomIt last, Compare comp);

// Since C++17 — execution policy overloads
template<class ExecutionPolicy, class RandomIt>
void sort(ExecutionPolicy&& policy, RandomIt first, RandomIt last);

// Since C++20 — ranges, with optional comparator and projection
namespace ranges {
    template<std::random_access_range R,
             class Comp = ranges::less,
             class Proj = std::identity>
    borrowed_iterator_t<R> sort(R&& r, Comp comp = {}, Proj proj = {});
}

comp(a, b) returns true if a should precede b. The default is std::less<>{} (C++14 transparent version), which invokes operator<.

Examples

std::sort — General Purpose

std::sort typically implements introsort: quicksort for the bulk of the work, heapsort when recursion depth exceeds O(log n) to avoid O(n²) worst-case, and insertion sort for small subsequences. Result: O(n log n) worst case with low constant in practice.

cpp

#include <algorithm>
#include <vector>

std::vector<int> v{5, 3, 8, 1, 9, 2, 7, 4, 6};

std::sort(v.begin(), v.end());                       // ascending
std::sort(v.begin(), v.end(), std::greater<int>{});  // descending

// Sort a subrange
std::sort(v.begin() + 2, v.begin() + 5);

// C-style array — pointers are random-access iterators (since C++98)
int arr[] = {5, 3, 8, 1};
std::sort(std::begin(arr), std::end(arr));            // std::begin/end: C++11
std::sort(arr, arr + 4);                             // equivalent, works pre-C++11

// Multi-field sort: primary dept asc, secondary seniority desc, tertiary name asc
struct Employee { std::string dept; int seniority; std::string name; };
std::vector<Employee> employees = /* ... */;

std::sort(employees.begin(), employees.end(),
    [](const Employee& a, const Employee& b) {
        if (a.dept != b.dept)           return a.dept < b.dept;
        if (a.seniority != b.seniority) return a.seniority > b.seniority;
        return a.name < b.name;
    });

// Same-direction multi-field: std::tie is concise and correct
std::sort(employees.begin(), employees.end(),
    [](const Employee& a, const Employee& b) {
        return std::tie(a.dept, a.name) < std::tie(b.dept, b.name);
    });

std::stable_sort — Preserving Relative Order

Uses mergesort or timsort. Allocates O(n) auxiliary memory when available and achieves O(n log n); without it, falls back to O(n log² n) in-place merging.

cpp

struct Task { int priority; std::string name; };
std::vector<Task> tasks = {{10,"A"},{5,"B"},{10,"C"},{5,"D"}};

std::stable_sort(tasks.begin(), tasks.end(),
    [](const Task& a, const Task& b) { return a.priority < b.priority; });
// Guaranteed order: B, D, A, C — equal-priority tasks keep insertion order

Multi-pass stable sort sorts by secondary key first, then stable-sorts by primary:

cpp

// Sort employees: primary=dept asc, secondary=name asc
std::sort(employees.begin(), employees.end(),
    [](const Employee& a, const Employee& b) { return a.name < b.name; });
std::stable_sort(employees.begin(), employees.end(),
    [](const Employee& a, const Employee& b) { return a.dept < b.dept; });

std::partial_sort — Sorted Top-K

Places the k smallest elements, fully sorted, into [first, middle). The range [middle, last) contains the remaining elements in unspecified order. Complexity: O(n log k).

cpp

std::vector<int> v{5, 3, 8, 1, 9, 2, 7, 4, 6};

std::partial_sort(v.begin(), v.begin() + 3, v.end());
// v[0..2] = {1, 2, 3}; v[3..8] in unspecified order

// Copy variant — writes to a separate container, source unchanged
std::vector<int> top3(3);
std::partial_sort_copy(v.begin(), v.end(), top3.begin(), top3.end());

std::partial_sort_copy(v.begin(), v.end(), top3.begin(), top3.end(),
    std::greater<int>{});  // top3 = {9, 8, 7}

std::nth_element — Linear Partition

Rearranges so v[n] holds the value that would be there in a fully sorted sequence. Elements in [first, nth) are ≤ *nth; elements in (nth, last) are ≥ *nth. Neither partition is sorted. Complexity: O(n) average; most implementations use introselect for guaranteed O(n) worst case.

cpp

std::vector<int> v{5, 3, 8, 1, 9, 2, 7, 4, 6};

// Median in O(n)
auto mid = v.begin() + v.size() / 2;
std::nth_element(v.begin(), mid, v.end());
int median = *mid; // 5

// Top-3 values, unordered — faster than partial_sort when order doesn't matter
std::nth_element(v.begin(), v.begin() + 3, v.end(), std::greater<int>{});
// v[0..2] contains the 3 largest in arbitrary order

// 90th percentile
size_t idx = v.size() * 9 / 10;
std::nth_element(v.begin(), v.begin() + idx, v.end());
int p90 = v[idx];

std::ranges::sort (C++20)

The ranges version takes any std::random_access_range and accepts a projection — a callable applied to each element before comparison — eliminating boilerplate member-access lambdas.

cpp

#include <algorithm>
#include <ranges>

struct Person { std::string name; int age; };
std::vector<Person> people = {{"Alice", 30}, {"Bob", 25}, {"Carol", 35}};

std::ranges::sort(people, {}, &Person::age);              // asc by age
std::ranges::sort(people, std::greater{}, &Person::age);  // desc by age

// Projection can be any callable
std::ranges::sort(people, {}, [](const Person& p) { return p.name.size(); });

// Works on views — no .begin()/.end() required
auto first3 = people | std::views::take(3);               // C++20
std::ranges::sort(first3, {}, &Person::name);

// ranges::stable_sort, ranges::partial_sort, ranges::nth_element all exist (C++20)
std::ranges::stable_sort(people, {}, &Person::age);
std::ranges::nth_element(people, people.begin() + 1, {}, &Person::age);

Parallel Sorting (C++17)

cpp

#include <execution>

std::vector<int> v(1'000'000);

std::sort(std::execution::seq,     v.begin(), v.end()); // C++17: explicit sequential
std::sort(std::execution::par,     v.begin(), v.end()); // C++17: parallel (thread pool)
std::sort(std::execution::par_unseq, v.begin(), v.end()); // C++17: parallel + SIMD

par_unseq permits interleaving of iterations across threads and SIMD lanes; the comparator must be re-entrant and not acquire locks. On Linux with libstdc++/libc++, link -ltbb for par/par_unseq support.

Checking Sort State

cpp

bool ok   = std::is_sorted(v.begin(), v.end());                      // C++11
bool desc = std::is_sorted(v.begin(), v.end(), std::greater<int>{}); // C++11

auto it = std::is_sorted_until(v.begin(), v.end());  // C++11
// it == v.end() → fully sorted; otherwise *it is the first violation

Performance Summary

Algorithm	Avg	Worst	Stable	Extra Memory	When to use
`std::sort`	O(n log n)	O(n log n)	No	O(log n)	Default choice
`std::stable_sort`	O(n log n)†	O(n log² n)†	Yes	O(n) / O(log n)†	Equal elements must keep order
`std::partial_sort`	O(n log k)	O(n log k)	No	O(k)	Sorted top-k
`std::nth_element`	O(n)	O(n)‡	No	O(log n)	Median, unsorted top-k
`std::ranges::sort`	O(n log n)	O(n log n)	No	O(log n)	Ranges/projections (C++20)

† std::stable_sort achieves O(n log n) with O(n) auxiliary memory; without it, falls back to O(n log² n).
‡ Theoretically O(n²); most implementations use introselect for guaranteed O(n) worst case.

Best Practices

Prefer std::nth_element over std::partial_sort when order within the partition doesn't matter. O(n) vs O(n log k) — for large n and large k the difference is substantial.

Use projections in C++20 instead of comparator lambdas. std::ranges::sort(v, {}, &T::field) is shorter, harder to get wrong, and composes naturally with other ranges algorithms.

For multi-key same-direction sorts, std::tie is idiomatic and avoids bugs. For mixed-direction keys (some ascending, some descending), write the explicit if-chain — do not attempt to negate with std::tie.

Member sorts for std::list/std::forward_list preserve iterator validity. If you need sorted order without invalidating existing iterators into the list, the member sort() is the only option.

Common Pitfalls

Violating Strict Weak Ordering

The comparator must be irreflexive (!comp(a,a)), asymmetric, and transitive. Using <= instead of < violates irreflexivity and produces undefined behavior:

cpp

// UNDEFINED BEHAVIOR — comp(a,a) returns true, violating irreflexivity
std::sort(v.begin(), v.end(), [](int a, int b) { return a <= b; });

// Correct
std::sort(v.begin(), v.end(), [](int a, int b) { return a < b; });

MSVC's debug iterator and libstdc++'s debug mode assert on detected violations. In release builds the program may crash, infinite-loop, or silently corrupt data.

Assuming nth_element Partitions Are Sorted

After std::nth_element, only v[n] is correctly placed. The ranges [first, nth) and (nth, last) are unordered:

cpp

std::vector<int> v{5, 3, 8, 1, 9};
std::nth_element(v.begin(), v.begin() + 2, v.end());
// v[2] is correct; v[0] is NOT necessarily the minimum
int lower_min = *std::min_element(v.begin(), v.begin() + 2); // correct approach

Expecting std::sort to Preserve Equal-Element Order

std::sort is not stable. If correctness depends on equal elements retaining their original relative order, you must use std::stable_sort:

cpp

std::vector<Task> tasks = {{1,"B"},{2,"A"},{1,"C"}};
std::sort(tasks.begin(), tasks.end(),
    [](const Task& a, const Task& b) { return a.priority < b.priority; });
// B and C (equal priority) may appear in either order — use stable_sort if order matters

Custom comparators and projections (C++20 ranges)

Projections decouple what to sort from how to compare. A projection is a callable that transforms each element before the comparator sees it, removing the need to embed member access inside every lambda.

cpp

// C++20
#include <algorithm>
#include <ranges>
#include <string>
#include <vector>

struct Product {
    std::string name;
    double price;
    int stock;
};

std::vector<Product> catalog = {
    {"Widget", 9.99, 100}, {"Gadget", 24.99, 5}, {"Doohickey", 4.49, 250}
};

// Project onto a data member — no lambda needed
std::ranges::sort(catalog, {}, &Product::price);           // asc by price
std::ranges::sort(catalog, std::greater{}, &Product::stock); // desc by stock

// Project with a callable — sort by name length, then alphabetically
std::ranges::sort(catalog,
    [](auto a, auto b) { return a < b; },
    [](const Product& p) { return std::tie(p.name.size(), p.name); });

// Compose projections across algorithms — min_element, max_element, etc.
auto cheapest = std::ranges::min_element(catalog, {}, &Product::price);
auto priciest = std::ranges::max_element(catalog, {}, &Product::price);

Comparators still must satisfy strict weak ordering. Projections do not relax that requirement — they only transform the values fed to the comparator. Applying std::greater{} to projected values is well-defined because std::greater still computes b < a.

cpp

// C++20 — custom three-field comparator with projection
std::ranges::sort(catalog,
    [](const auto& a, const auto& b) {
        if (a.stock != b.stock) return a.stock > b.stock; // most stock first
        return a.price < b.price;                          // then cheapest
    },
    std::identity{});  // identity projection — explicit no-op

Sorting with three-way comparison (`operator<=>`)

operator<=> (the spaceship operator, C++20) enables a single definition that drives all six comparison operators. When a type defines <=>, std::sort can use operator< derived from it, and std::ranges::sort can use std::compare_three_way as its comparator.

cpp

// C++20
#include <compare>
#include <algorithm>

struct Version {
    int major, minor, patch;

    // defaulted <=> generates <, <=, >, >=, ==, != automatically
    auto operator<=>(const Version&) const = default;
};

std::vector<Version> releases = {{1,0,0}, {2,1,3}, {1,9,0}, {2,0,1}};
std::sort(releases.begin(), releases.end()); // uses synthesized operator<

// Explicit three-way comparator with ranges
std::ranges::sort(releases, std::compare_three_way{});

Custom spaceship for non-lexicographic order can return one of three ordering types: std::strong_ordering (total, no incomparable elements), std::weak_ordering (allows equivalence classes), or std::partial_ordering (allows incomparable pairs, e.g. NaN in floats).

cpp

// C++20 — weak ordering for case-insensitive string comparison
#include <cctype>
struct CIString {
    std::string s;
    std::weak_ordering operator<=>(const CIString& o) const {
        for (size_t i = 0; i < std::min(s.size(), o.s.size()); ++i) {
            auto c = std::tolower((unsigned char)s[i]);
            auto d = std::tolower((unsigned char)o.s[i]);
            if (c < d) return std::weak_ordering::less;
            if (c > d) return std::weak_ordering::greater;
        }
        return s.size() <=> o.s.size();
    }
};

std::vector<CIString> words = {{"Banana"}, {"apple"}, {"Cherry"}};
std::ranges::sort(words); // alphabetical, case-insensitive

Do not use std::partial_ordering as the return type for a sort comparator unless all elements are actually comparable — a comparator that can return unordered will violate strict weak ordering and produce undefined behavior.

Partial sort and nth_element

std::partial_sort and std::nth_element solve complementary sub-problems of sorting — the first gives a fully sorted prefix, the second only guarantees correct placement of one pivot.

cpp

// C++98/11
#include <algorithm>
#include <vector>

std::vector<double> scores = {88.5, 72.0, 95.3, 60.1, 91.7, 55.4, 83.2};

// --- partial_sort: top-3 fully sorted ---
std::partial_sort(scores.begin(), scores.begin() + 3, scores.end(),
    std::greater<double>{});
// scores[0..2] = {95.3, 91.7, 88.5} — guaranteed sorted
// scores[3..6] = unspecified

// --- partial_sort_copy: non-destructive, writes to separate output ---
std::vector<double> top3(3);
std::partial_sort_copy(scores.begin(), scores.end(),
                       top3.begin(), top3.end(),
                       std::greater<double>{});

// --- nth_element: median-of-seven in O(n) ---
auto mid = scores.begin() + scores.size() / 2;
std::nth_element(scores.begin(), mid, scores.end());
double median = *mid;

// --- nth_element + sort: sort only top-k, when k << n ---
// Partition top-3 (O(n)), then sort just those 3 (O(k log k))
std::nth_element(scores.begin(), scores.begin() + 3, scores.end(),
    std::greater<double>{});
std::sort(scores.begin(), scores.begin() + 3, std::greater<double>{});

Ranges counterparts exist in C++20. std::ranges::partial_sort, std::ranges::partial_sort_copy, and std::ranges::nth_element all accept projections and follow the same complexity contracts.

cpp

// C++20
std::ranges::nth_element(scores, scores.begin() + 2, std::greater{});
// scores[2] == third-highest value; halves below/above are unordered

Stable sort guarantees

Stability means equal elements emerge in their original relative order. This property is invisible when all elements are unique but becomes critical when sorting objects by one key that leaves others equivalent.

cpp

// C++98
#include <algorithm>
#include <vector>
#include <string>

struct LogEntry {
    int severity;    // 1=info, 2=warn, 3=error
    std::string msg;
    int timestamp;   // already in insertion order
};

std::vector<LogEntry> log = {
    {2,"disk warn",1}, {1,"startup",2}, {3,"crash",3},
    {2,"net warn",4},  {1,"tick",5}
};

// stable_sort: equal-severity entries retain their timestamp order
std::stable_sort(log.begin(), log.end(),
    [](const LogEntry& a, const LogEntry& b) {
        return a.severity < b.severity;
    });
// Result order by severity: startup(1), tick(1), disk warn(2), net warn(2), crash(3)

// std::sort gives no such guarantee for equal-severity entries

Multi-pass radix-style sort exploits stability: sort by least-significant key first, then stable-sort by each more-significant key in turn.

cpp

// C++11 — sort employees: primary=dept asc, secondary=seniority desc
std::stable_sort(employees.begin(), employees.end(),
    [](const Employee& a, const Employee& b) { return a.seniority > b.seniority; });
std::stable_sort(employees.begin(), employees.end(),
    [](const Employee& a, const Employee& b) { return a.dept < b.dept; });
// Final order: within each dept, highest seniority first

std::stable_sort allocates O(n) temporary storage when the allocator allows it. Without auxiliary memory, it performs O(n log² n) in-place merges. On most platforms temporary allocation succeeds, keeping the practical complexity at O(n log n).

Sorting strings and locale

String sorting is locale-sensitive. The default std::sort on std::string compares bytes via char values (operator<), which gives ASCII order, not lexicographic order in the user's locale. Use std::locale and std::collate for locale-correct ordering.

cpp

// C++11
#include <algorithm>
#include <locale>
#include <string>
#include <vector>

std::vector<std::string> words = {"Ångström", "apple", "éclair", "Banana"};

// Default: byte order (ASCII) — uppercase before lowercase, accents after z
std::sort(words.begin(), words.end());

// Locale-aware collation
std::locale loc("en_US.UTF-8");
const auto& coll = std::use_facet<std::collate<char>>(loc);

std::sort(words.begin(), words.end(),
    [&](const std::string& a, const std::string& b) {
        return coll.compare(a.data(), a.data() + a.size(),
                            b.data(), b.data() + b.size()) < 0;
    });

For case-insensitive ASCII-only sorting, a simple transform comparator suffices without locale overhead.

cpp

// C++11
#include <cctype>
std::sort(words.begin(), words.end(),
    [](const std::string& a, const std::string& b) {
        return std::lexicographical_compare(
            a.begin(), a.end(), b.begin(), b.end(),
            [](char x, char y) {
                return std::tolower((unsigned char)x) <
                       std::tolower((unsigned char)y);
            });
    });

std::u8string (C++20) and std::u32string enable Unicode-aware sorting, but full Unicode collation (DUCET rules) requires an external library such as ICU — the standard library does not implement the Unicode Collation Algorithm.

Parallel sort (C++17)

Execution policies unlock hardware parallelism without changing the algorithm's interface. Passing std::execution::par or std::execution::par_unseq to std::sort tells the implementation it may distribute work across threads (and SIMD lanes for par_unseq).

cpp

// C++17
#include <algorithm>
#include <execution>
#include <vector>
#include <numeric>

std::vector<double> data(10'000'000);
std::iota(data.begin(), data.end(), 0.0);  // fill with 0,1,...

// Sequential — baseline
std::sort(std::execution::seq, data.begin(), data.end());

// Parallel — may use a thread pool (TBB on Linux, PPL on MSVC)
std::sort(std::execution::par, data.begin(), data.end());

// Parallel + vectorised — threads AND SIMD; comparator must be re-entrant
std::sort(std::execution::par_unseq, data.begin(), data.end());

// Custom comparator with parallel sort — still valid, must be stateless/re-entrant
std::sort(std::execution::par, data.begin(), data.end(), std::greater<double>{});

Platform notes. GCC/libstdc++ requires linking -ltbb (Intel TBB) for par/par_unseq — without it the policy silently falls back to sequential on some versions. MSVC ships PPL and parallelises automatically. Apple Clang supports execution policies from macOS 10.15+ (Catalina). Check __cpp_lib_parallel_algorithm (value 201603L) to confirm availability at compile time.

cpp

// C++17 — feature-test macro
#ifdef __cpp_lib_parallel_algorithm
    std::sort(std::execution::par, v.begin(), v.end());
#else
    std::sort(v.begin(), v.end()); // fallback
#endif

par_unseq forbids the comparator from acquiring mutexes, calling non-reentrant functions, or storing thread-local state — violations are undefined behavior. For stable parallel sorting, std::stable_sort with std::execution::par is also supported.

Choosing the right sort algorithm

The default choice is std::sort, but each algorithm has a regime where it dominates. Use this decision guide to pick the fastest algorithm for the task at hand.

Goal	Best algorithm	Reason
Sort entire sequence	`std::sort`	Introsort, lowest constant factor
Sort and preserve equal-element order	`std::stable_sort`	Mergesort, stable by definition
Retrieve fully sorted top-k	`std::partial_sort`	O(n log k) — skips sorting the tail
Find k-th element / median	`std::nth_element`	O(n) introselect, no sorting needed
Top-k then examine order	`nth_element` + `sort` on prefix	O(n) partition + O(k log k) sort
Sort > 1 M elements with multiple cores	`std::sort` + `par` policy	Scales with core count
Sort list / forward_list	`.sort()` member	Only option — no random-access iterators
Sort with projection (C++20)	`std::ranges::sort`	Cleaner than lambda member access

Small sizes favour insertion sort. Most std::sort implementations switch to insertion sort for subsequences of ≤ 16–32 elements; there is no benefit to hand-rolling this.

cpp

// C++20 — idiomatic decision tree in code
void sort_products(std::vector<Product>& v, bool need_stable) {
    if (need_stable) {
        std::ranges::stable_sort(v, {}, &Product::price); // C++20
    } else {
        std::ranges::sort(v, {}, &Product::price);        // C++20
    }
}

// When you only need top-10 out of 1 million records:
void top10_by_price(std::vector<Product>& v) {
    // O(n) partition first, then O(k log k) sort of the prefix
    std::ranges::nth_element(v, v.begin() + 10, std::greater{}, &Product::price); // C++20
    std::ranges::sort(v.begin(), v.begin() + 10, std::greater{}, &Product::price); // C++20
}

Never write your own sort for general use. std::sort has decades of cache-aware, branch-predictor-friendly tuning. Custom hand-written sorts are almost always slower except in highly specialized circumstances (e.g., fixed-width radix sort on integers).

See Also

std::merge / std::inplace_merge — merging pre-sorted ranges
std::lower_bound / std::upper_bound — binary search requiring a sorted range
std::make_heap / std::sort_heap — sort_heap on a max-heap yields ascending order in O(n log n)
Comparators and Strict Weak Ordering — std::less, std::greater, transparent std::less<> (C++14)
Execution Policies — std::execution::seq, par, par_unseq (C++17)