C++ Sorting: std::sort, Custom Comparators & Stable Sort

Sorting Is Just Another Algorithm

On the previous page you saw that the standard library ships ready-made algorithms that work on any range through iterators. Sorting is the one you'll reach for most often, and it gets its own page because it has a few sharp edges - custom orderings, stability, and a rule that, if you break it, hands you undefined behavior instead of a wrong answer.

The workhorse is std::sort from <algorithm>. You give it the beginning and end of a range, and it rearranges the elements in place into ascending order:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {5, 2, 8, 1, 9, 3};

    sort(nums.begin(), nums.end());   // ascending, in place

    for (int n : nums) cout << n << " ";  // 1 2 3 5 8 9
    cout << "\n";
    return 0;
}

No copy is made - the vector itself is reordered. Under the hood std::sort is typically an introsort (quicksort that falls back to heapsort), giving you O(n log n) on average. That's almost always faster and far less error-prone than writing your own sort.

It works on plain C arrays too - you just describe the range with pointers:

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int arr[] = {40, 10, 30, 20};
    int n = 4;

    sort(arr, arr + n);               // or sort(begin(arr), end(arr));

    for (int x : arr) cout << x << " ";  // 10 20 30 40
    return 0;
}

Custom Order with a Comparator

By default std::sort orders elements with operator<. To sort differently, pass a third argument: a comparator that takes two elements and returns true if the first should come before the second.

A lambda is the natural fit. Descending order is just a > b:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {5, 2, 8, 1, 9, 3};

    sort(nums.begin(), nums.end(), [](int a, int b) {
        return a > b;   // "a before b" when a is larger -> descending
    });

    for (int n : nums) cout << n << " ";  // 9 8 5 3 2 1
    cout << "\n";
    return 0;
}

For the common case of plain descending order on built-in types, the library even ships a ready-made comparator, greater<T>() from <functional>:

#include <functional>
sort(nums.begin(), nums.end(), greater<int>());  // same as a > b

The comparator is also how you sort by something other than the value itself - for example, sorting strings by length rather than alphabetically:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    vector<string> words = {"pear", "fig", "banana", "kiwi"};

    sort(words.begin(), words.end(), [](const string& a, const string& b) {
        return a.size() < b.size();   // shorter words first
    });

    for (const string& w : words) cout << w << " ";  // fig kiwi pear banana
    cout << "\n";
    return 0;
}

Take the comparator parameters by const& for anything bigger than a couple of bytes (like string) - copying every element on every comparison is pure waste.

Sorting Structs by a Field

In real programs you usually sort collections of structs by one of their fields. The comparator just reaches into the field you care about. Here we sort people by age, youngest first:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct Person {
    string name;
    int age;
};

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return a.age < b.age;
    });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";
    return 0;
}

Notice that Linus and Dennis both have age 25. They came out in their original relative order here, but std::sort does not guarantee that. If the relative order of equal elements matters, use std::stable_sort, which preserves it (at a small performance cost):

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct Person { string name; int age; };

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    stable_sort(people.begin(), people.end(),
        [](const Person& a, const Person& b) { return a.age < b.age; });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";
    // Linus stays before Dennis - their input order is preserved
    return 0;
}

To break ties deliberately - say, sort by age, then alphabetically by name - compare the secondary key only when the primary keys are equal. std::tie makes this clean:

#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <algorithm>
using namespace std;

struct Person { string name; int age; };

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return tie(a.age, a.name) < tie(b.age, b.name);  // age, then name
    });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";  // Dennis & Linus 25, alphabetical
    return 0;
}

The Strict-Weak-Ordering Trap

This is the single most dangerous mistake in C++ sorting, because it doesn't give you a wrong answer - it gives you undefined behavior, which often means a crash or out-of-bounds read.

std::sort requires your comparator to define a strict weak ordering. The practical rule: comp(x, x) must be false for any element x. In other words, an element is never "before" itself. That's exactly what < and > give you, and exactly what <= and >= break:

// BUG: returns true when a == b, violating strict weak ordering.
sort(v.begin(), v.end(), [](int a, int b) {
    return a <= b;   // undefined behavior - may crash on some inputs
});

With <=, the comparator claims 5 comes before another 5, which is contradictory. std::sort may then walk a pointer past the end of the range. Tiny inputs sometimes appear to work, which makes this bug terrifying - it can pass your tests and crash in production. The fix is simply <:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};

    sort(v.begin(), v.end(), [](int a, int b) {
        return a < b;   // correct: false when equal
    });

    for (int x : v) cout << x << " ";
    cout << "\n";
    return 0;
}

A second classic gotcha: sorting invalidates anything pointing into the range. Iterators, pointers, and indices you saved before the sort no longer refer to the same logical element afterward, because the elements moved. Re-derive any position you need after sorting, never before.

Sorting Part of a Range

Sometimes you don't need everything sorted - you just want the top few. Sorting the whole vector to read the first three is wasteful. std::partial_sort arranges only the elements you ask for and leaves the rest in unspecified order, which is cheaper:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 7};

    // Put the 3 smallest, in order, at the front. Rest is unspecified.
    partial_sort(v.begin(), v.begin() + 3, v.end());

    for (int i = 0; i < 3; i++) cout << v[i] << " ";  // 1 2 3
    cout << "\n";
    return 0;
}

And if you only need the single element that would sit at a given position - like the median - std::nth_element does even less work: it places the right element at that index, with everything smaller before it and everything larger after, all in O(n) on average.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 7};
    size_t mid = v.size() / 2;

    nth_element(v.begin(), v.begin() + mid, v.end());

    cout << "median is " << v[mid] << "\n";  // 5
    return 0;
}

Reach for these when "fully sorted" is more than the problem actually needs - they save real time on large data.

Next: Templates

Have you noticed that the same std::sort handled int, string, and your own Person struct, and greater<int>() could just as easily be greater<string>()? That generality isn't magic - it's templates, the mechanism that lets one piece of code work for any type the caller plugs in. On the next page we'll see how to write your own templated functions and classes, so your code can be as type-agnostic as the algorithms you've been using.