C++ Sorting Algorithms

Sorting means arranging the elements of a collection — numbers, strings, or custom objects — into a defined order, typically ascending or descending. It is one of the most fundamental operations in computer science: searching, deduplication, scheduling, and many other algorithms become dramatically faster (or only become possible) once data is sorted. C++ ships a highly optimized std::sort in the Standard Library, so you rarely need to hand-write a sorting routine, but understanding how sorting actually works — comparators, stability, and complexity — is essential for writing correct, efficient C++ programs.

Overview / How Sorting Works

Almost every general-purpose sort in C++ is a comparison-based sort: the algorithm repeatedly asks "is element A less than element B?" and rearranges elements based on the answers. This means any type you want to sort just needs a way to compare two elements — either the built-in < operator or a comparator function you supply. It is a mathematical fact that any comparison-based sort needs at least O(n log n) comparisons in the worst case to sort n elements — you cannot do better using only pairwise comparisons.

The C++ Standard Library’s std::sort (declared in <algorithm>) is not a single fixed algorithm. Most implementations use introsort: it starts with quicksort (fast on average, in-place, cache-friendly), switches to heapsort if the recursion goes too deep (protecting against quicksort’s O(n²) worst case), and switches to insertion sort for very small sub-ranges (where its low constant overhead beats quicksort’s overhead). This hybrid strategy gives std::sort a guaranteed O(n log n) worst case while staying fast in practice. std::sort is not stable: elements that compare equal may be reordered relative to each other. If you need equal elements to keep their original relative order, use std::stable_sort, which is typically implemented with merge sort (O(n log n), but may use extra memory).

Under the hood, sorting a std::vector works directly on the underlying contiguous array using iterators (really pointers) — elements are swapped or moved in place, so no new container is allocated by std::sort itself. Because C++ move semantics apply, sorting large objects (like strings) is efficient: the algorithm moves data rather than deep-copying it wherever possible.

Syntax

#include <algorithm>

std::sort(first, last);
std::sort(first, last, comparator);
std::stable_sort(first, last, comparator);
Part Meaning
first Iterator to the first element of the range to sort (e.g. v.begin()).
last Iterator one-past-the-last element (e.g. v.end()). The range is [first, last).
comparator Optional callable taking two elements and returning true if the first should come before the second. Defaults to operator<.

A comparator must implement a strict weak ordering: it must be false when comparing an element to itself, and it must be consistent (never say A < B and B < A at the same time). Violating this causes undefined behavior, discussed under Common Mistakes.

Examples

Example 1: Sorting a vector of integers

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

int main() {
    vector<int> nums = {5, 2, 9, 1, 5, 6};
    sort(nums.begin(), nums.end());
    for (int n : nums) cout << n << " ";
    cout << endl;
    return 0;
}
Output:
1 2 5 5 6 9

By default std::sort uses operator<, so calling it with just a begin and end iterator sorts in ascending order. This is the form you will use most often.

Example 2: Descending order with a lambda comparator

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

int main() {
    vector<int> nums = {5, 2, 9, 1, 5, 6};
    sort(nums.begin(), nums.end(), [](int a, int b) {
        return a > b;
    });
    for (int n : nums) cout << n << " ";
    cout << endl;
    return 0;
}
Output:
9 6 5 5 2 1

Passing a lambda that returns a > b flips the ordering to descending. You could equally use std::greater<int>() from <functional> instead of writing your own lambda.

Example 3: Sorting objects by multiple keys

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

struct Student {
    string name;
    int score;
};

int main() {
    vector<Student> students = {
        {"Alice", 85},
        {"Bob", 92},
        {"Carol", 85},
        {"Dave", 78}
    };

    sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
        if (a.score != b.score) return a.score > b.score;
        return a.name < b.name;
    });

    for (const auto& s : students) {
        cout << s.name << ": " << s.score << endl;
    }
    return 0;
}
Output:
Bob: 92
Alice: 85
Carol: 85
Dave: 78

Here the comparator sorts primarily by score (descending); when two students tie on score, it falls back to comparing names alphabetically. This "compare by primary key, then tiebreak by secondary key" pattern is extremely common when sorting real-world records.

Under the Hood: A Manual Bubble Sort

To understand what a sorting algorithm actually does to memory, it helps to implement one by hand. Bubble sort repeatedly walks through the array, comparing each pair of adjacent elements and swapping them if they are out of order. Larger values "bubble" toward the end with each pass.

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

int main() {
    vector<int> arr = {64, 25, 12, 22, 11};
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
    for (int x : arr) cout << x << " ";
    cout << endl;
    return 0;
}
Output:
11 12 22 25 64

Step by step: the outer loop runs n - 1 passes. On each pass, the inner loop scans left to right, swapping any adjacent pair that is out of order. After the first pass, the largest element is guaranteed to be at the end, so the next pass can safely ignore it (that is what n - i - 1 achieves). This makes bubble sort O(n²) in the worst and average case — fine for teaching or tiny arrays, but far too slow for real workloads, which is exactly why the Standard Library gives you std::sort instead.

Common Sorting Algorithms Compared

Algorithm Average Time Worst Time Space Stable?
Bubble Sort O(n²) O(n²) O(1) Yes
Selection Sort O(n²) O(n²) O(1) No
Insertion Sort O(n²) O(n²) O(1) Yes
Merge Sort O(n log n) O(n log n) O(n) Yes
Quicksort O(n log n) O(n²) O(log n) No
std::sort (introsort) O(n log n) O(n log n) O(log n) No
std::stable_sort O(n log n) O(n log n) O(n) Yes

Common Mistakes

Mistake 1: Forgetting to include <algorithm>

Some standard library implementations happen to pull in <algorithm> transitively through <vector> or other headers, so this mistake can appear to work and then break the moment you switch compilers or standard library versions.

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

int main() {
    vector<int> v = {3, 1, 2};
    sort(v.begin(), v.end());
    for (int x : v) cout << x << " ";
    return 0;
}

Fix: always explicitly include <algorithm> when you use std::sort, regardless of what other headers you already have.

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

int main() {
    vector<int> v = {3, 1, 2};
    sort(v.begin(), v.end());
    for (int x : v) cout << x << " ";
    cout << endl;
    return 0;
}
Output:
1 2 3

Mistake 2: A comparator that is not a strict weak ordering

It is tempting to write >= when you want descending order, but a correct comparator must return false when comparing an element to itself. Using >= breaks this rule and causes undefined behavior — possibly a crash, an infinite loop, or silently wrong output, depending on the implementation.

vector<int> v = {3, 1, 2};
sort(v.begin(), v.end(), [](int a, int b) {
    return a >= b; // WRONG: violates strict weak ordering, undefined behavior
});

Fix: use a strict comparison (> for descending, < for ascending), never >= or <=.

vector<int> v = {3, 1, 2};
sort(v.begin(), v.end(), [](int a, int b) {
    return a > b;
});
for (int x : v) cout << x << " ";
Output:
3 2 1

Best Practices

  • Prefer std::sort over hand-written algorithms; it is heavily optimized and well tested.
  • Use std::stable_sort whenever the relative order of equal elements matters (e.g. sorting already-sorted data by a secondary key).
  • Write comparators using strict operators (< or >), never <= or >=.
  • For custom types, either overload operator< for the "natural" ordering or pass a lambda/comparator for one-off orderings — don’t force one canonical order if the type is sorted differently in different places.
  • If you only need the k smallest/largest elements, use std::partial_sort or std::nth_element instead of sorting the whole range — both are faster when k is much smaller than n.
  • Remember std::sort works on random-access iterators (vectors, arrays, deques); for std::list, use its member function list::sort() instead.

Practice Exercises

  1. Implement selection sort by hand on a vector<int>: on each pass, find the minimum of the unsorted portion and swap it into place. Print the sorted array.
  2. Given a vector<pair<string, int>> of (name, age) pairs, use std::sort with a lambda to sort by age in descending order.
  3. Given a vector<string> of words, sort them first by length (shortest first), and for words of equal length, sort alphabetically.

Summary

  • Sorting arranges data into order and is bounded by O(n log n) comparisons for comparison-based algorithms.
  • std::sort (from <algorithm>) is a fast, in-place, but unstable O(n log n) sort using an introsort hybrid strategy.
  • std::stable_sort preserves the relative order of equal elements, at the cost of extra memory.
  • Comparators must implement a strict weak ordering — using <=/>= causes undefined behavior.
  • Simple O(n²) algorithms like bubble sort are valuable for learning how sorting works, but should not be used in production code.
  • Use partial_sort or nth_element when you only need part of the sorted result.