STL Sorting and Partitioning

Prereqs Iterators, comparators (strict weak ordering), lambdas

Standard C++98 (sort, stable_sort, partition), improved in C++11/17/20

Frequently Asked Questions

QWhy can't std::sort work on std::list?

Astd::sort requires random-access iterators because it uses index-based swaps and partitioning (introsort). std::list provides only bidirectional iterators, so std::sort cannot compile with list iterators. Use the member function list.sort() instead, which is an O(n log n) merge sort optimized for linked-list node relinking.

QIs std::sort stable?

ANo. std::sort is typically implemented as introsort (quicksort with heapsort fallback) and does NOT preserve the relative order of equal elements. If you need stability, use std::stable_sort, which guarantees that equal elements retain their original order. It uses merge sort and may allocate extra memory.

QCan I use parallel execution policies with sorting algorithms?

AYes, since C++17. Pass std::execution::par or std::execution::par_unseq as the first argument: std::sort(std::execution::par, v.begin(), v.end()). Include <execution> and link against the TBB library (on most implementations). Note that the comparator must be thread-safe.

QWhat are the exact requirements for a comparator?

AA comparator must define a strict weak ordering: (1) irreflexivity -- comp(a, a) must be false, (2) asymmetry -- if comp(a, b) then !comp(b, a), (3) transitivity -- if comp(a, b) and comp(b, c) then comp(a, c). Using <= instead of < violates irreflexivity and causes undefined behavior, potentially including infinite loops or crashes.

C++

#include <iostream>
#include <format>
#include <vector>
#include <algorithm>
#include <string>
#include <cstdlib>

// Helper: print a vector
void print(std::string_view label, const std::vector<int>& v) {
    std::cout << label << ": ";
    for (int n : v) std::cout << n << ' ';
    std::cout << '\n';
}

C++

int main() {

1 std::sort -- O(n log n) introsort (quicksort + heapsort)

What

Ranges compose algorithms and views into lazy, pipeline-style transformations.

When

Use them for readable data-processing chains over containers and iterables.

Why

They reduce temporary containers and improve expression-level clarity.

Use

Compose with `|` and call range algorithms on views/containers.

C++ Version C++20

Sorts the range in-place. Not stable.

iterators. For std::list use the member function .sort() instead.

Watch out: std::sort requires random-access

Watch out: the comparator must define a strict weak ordering -- comp(a,a) must return false. Using <= instead of < causes undefined behavior.

C++

std::cout << "--- std::sort ---\n";
    std::vector<int> nums = {5, 2, 8, 1, 9, 3, 7, 4, 6};

    std::sort(nums.begin(), nums.end());
    print("Ascending", nums);

    std::sort(nums.begin(), nums.end(), std::greater<>());
    print("Descending", nums);

    // Custom comparator: sort by absolute distance from 5
    //
    std::sort(nums.begin(), nums.end(), [](int a, int b) {
        return std::abs(a - 5) < std::abs(b - 5);
    });
    print("By distance from 5", nums);

2 std::stable_sort -- preserves relative order of equal elements

What

std::stable_sort -- preserves relative order of equal elements.

When

Important when sorting by one field while preserving another.

Why

Important when sorting by one field while preserving another.

Use

Use it in code like: std::cout << "\n--- std::stable_sort ---\n";.

C++ Version Not explicitly specified in this example.

Important when sorting by one field while preserving another.

C++

std::cout << "\n--- std::stable_sort ---\n";
    struct Student {
        std::string name;
        int grade;
    };

    std::vector<Student> students = {
        {"Alice", 90}, {"Bob", 85}, {"Carol", 90},
        {"Dave", 85}, {"Eve", 95}
    };

    std::stable_sort(students.begin(), students.end(),
        [](const Student& a, const Student& b) {
            return a.grade > b.grade;  // Sort by grade descending
        });

    std::cout << "By grade (stable):\n";
    for (const auto& s : students) {
        std::cout << std::format("  {} ({})\n", s.name, s.grade);
    }
    // Alice still comes before Carol (both 90) -- stability preserved

3 std::partial_sort -- sort only the top K elements

What

std::partial_sort -- sort only the top K elements.

When

O(n log k) -- faster than full sort when k << n.

Why

O(n log k) -- faster than full sort when k << n.

Use

Use it in code like: std::cout << "\n--- std::partial_sort ---\n";.

C++ Version Not explicitly specified in this example.

O(n log k) -- faster than full sort when k << n.

C++

std::cout << "\n--- std::partial_sort ---\n";
    std::vector<int> data = {50, 20, 80, 10, 90, 30, 70, 40, 60};

    // Get the top 3 smallest elements in sorted order
    std::partial_sort(data.begin(), data.begin() + 3, data.end());
    print("Top 3 sorted", data);  // First 3 are sorted, rest is unspecified

4 std::nth_element -- find the nth smallest in O(n)

What

std::nth_element -- find the nth smallest in O(n).

When

Use this when it cleanly solves the problem in front of you.

Why

Places the nth element in its correct sorted position.

Use

Use it in code like: std::cout << "\n--- std::nth_element ---\n";.

C++ Version Not explicitly specified in this example.

Places the nth element in its correct sorted position. Elements before it are <= and elements after are >=.

C++

std::cout << "\n--- std::nth_element ---\n";
    data = {50, 20, 80, 10, 90, 30, 70, 40, 60};

    // Find the median (4th element in 0-indexed for 9 elements)
    std::nth_element(data.begin(), data.begin() + 4, data.end());
    std::cout << std::format("Median: {}\n", data[4]);

5 std::partition -- divide into two groups

What

std::partition -- divide into two groups.

When

Use this when it cleanly solves the problem in front of you.

Why

Elements satisfying the predicate come first.

Use

Use it in code like: std::cout << "\n--- std::partition ---\n";.

C++ Version Not explicitly specified in this example.

Elements satisfying the predicate come first.

C++

std::cout << "\n--- std::partition ---\n";
    std::vector<int> values = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    // Partition: evens first, then odds
    auto pivot = std::partition(values.begin(), values.end(),
        [](int n) { return n % 2 == 0; });

    std::cout << "Evens: ";
    for (auto it = values.begin(); it != pivot; ++it)
        std::cout << *it << ' ';
    std::cout << "\nOdds:  ";
    for (auto it = pivot; it != values.end(); ++it)
        std::cout << *it << ' ';
    std::cout << '\n';

6 Checking if sorted

What

Checking if sorted.

When

Use this when it cleanly solves the problem in front of you.

Why

It improves correctness, clarity, and maintainability.

Use

Use it in code like: std::cout << "\n--- std::is_sorted ---\n";.

C++ Version Not explicitly specified in this example.

C++

std::cout << "\n--- std::is_sorted ---\n";
    std::vector<int> sorted_vec = {1, 2, 3, 4, 5};
    std::vector<int> unsorted_vec = {1, 3, 2, 5, 4};

    std::cout << std::format("sorted_vec sorted? {}\n",
                              std::is_sorted(sorted_vec.begin(), sorted_vec.end()));
    std::cout << std::format("unsorted_vec sorted? {}\n",
                              std::is_sorted(unsorted_vec.begin(), unsorted_vec.end()));

    // Find where sorting breaks
    auto until = std::is_sorted_until(unsorted_vec.begin(), unsorted_vec.end());
    std::cout << std::format("Sorted until position {}\n",
                              std::distance(unsorted_vec.begin(), until));

    return 0;
}