C++AlgorithmsBeginner

std::sort()

Sorts the elements in a range `[first, last)` in non-descending order.

Review the syntaxStudy the examplesOpen the coding app
std::sort(first, last, [comp]);
Open Coding Reference

This static page keeps the syntax and examples indexed for search, while the coding app handles interactive exploration and saved references.

What it does

Overview

Sorts the elements in a range `[first, last)` in non-descending order.

The `std::sort()` algorithm is a highly efficient and versatile function from the `<algorithm>` header used to sort elements within a specified range. It typically implements an IntroSort algorithm, which is a hybrid sorting algorithm combining QuickSort, HeapSort, and InsertionSort to provide good average-case performance (O(N log N)) while avoiding QuickSort's worst-case O() behavior. The function takes two iterators, `first` and `last`, defining the half-open range `[first, last)` to be sorted. By default, it sorts elements in non-descending order using `operator<` for comparison. An optional third argument, `comp`, can be provided as a custom comparison function (a lambda, function pointer, or functor) to define a different sorting order (e.g., descending, or based on a specific attribute of custom objects). `std::sort()` operates in-place, modifying the original container. It's a cornerstone algorithm in C++ for ordering data in vectors, arrays, or other containers that provide random-access iterators, making subsequent operations like searching much more efficient. It's important to note that `std::sort()` requires random-access iterators, meaning it works well with `std::vector`, `std::deque`, and raw arrays, but not with `std::list` (which requires `list::sort()`).

Quick reference

Syntax

std::sort(first, last, [comp]);

Inputs

Parameters

firstRandomAccessIterator · An iterator to the beginning of the range to sort.
lastRandomAccessIterator · An iterator to the end of the range (one past the last element).
comp (optional)Compare · An optional binary predicate that returns true if the first argument is considered less than the second.

See it in practice

Examples

1

Sorting a vector of integers in ascending order

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> numbers = {5, 2, 8, 1, 9, 4};
    std::sort(numbers.begin(), numbers.end());

    std::cout << "Sorted numbers (ascending): ";
    for (int n : numbers) {
        std::cout << n << " ";
    }
    std::cout << std::endl;
    return 0;
}
Output:
Sorted numbers (ascending): 1 2 4 5 8 9

The `std::sort()` function is called with iterators to the beginning and end of the vector. By default, it sorts in ascending order.

2

Sorting a vector of strings in descending order using a lambda

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

int main() {
    std::vector<std::string> names = {"Alice", "Bob", "Charlie", "David"};
    std::sort(names.begin(), names.end(), [](const std::string& a, const std::string& b) {
        return a > b; // Custom comparison for descending order
    });

    std::cout << "Sorted names (descending): ";
    for (const std::string& name : names) {
        std::cout << name << " ";
    }
    std::cout << std::endl;
    return 0;
}
Output:
Sorted names (descending): David Charlie Bob Alice

A lambda expression is passed as the custom comparison function, `comp`, to sort the strings in descending lexicographical order.

3

Sorting a C-style array

#include <iostream>
#include <algorithm>

int main() {
    int arr[] = {30, 10, 50, 20, 40};
    int n = sizeof(arr) / sizeof(arr[0]);

    std::sort(arr, arr + n);

    std::cout << "Sorted array: ";
    for (int i = 0; i < n; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}
Output:
Sorted array: 10 20 30 40 50

`std::sort()` can also be used with raw C-style arrays by passing pointers to the beginning and one past the end of the array.

Debug faster

Common Errors

1

Compilation Error

Cause: Attempting to sort a container that does not provide random-access iterators (e.g., `std::list`).

Fix: For `std::list`, use its member function `list::sort()`. For other non-random-access containers, consider copying to a `std::vector`, sorting, and copying back, or using `std::stable_sort` with appropriate iterators if available.

#include <list>
#include <algorithm>
int main() {
    std::list<int> l = {3, 1, 2};
    std::sort(l.begin(), l.end()); // Compilation Error
    return 0;
}
2

Logical Error

Cause: Incorrect custom comparison function (`comp`) that does not establish a strict weak ordering (e.g., not transitive, or not strictly less than).

Fix: Ensure the comparison function returns `true` if the first argument should come before the second, `false` otherwise, and adheres to strict weak ordering rules.

std::sort(v.begin(), v.end(), [](int a, int b){ return a <= b; }); // Not strict weak ordering

Runtime support

Compatibility

GCC, Clang, MSVCN/AC++98+

Source: cppreference.com

Common questions

Frequently Asked Questions

Sorts the elements in a range `[first, last)` in non-descending order.

first: An iterator to the beginning of the range to sort. last: An iterator to the end of the range (one past the last element). comp: An optional binary predicate that returns true if the first argument is considered less than the second.

Compilation Error: For `std::list`, use its member function `list::sort()`. For other non-random-access containers, consider copying to a `std::vector`, sorting, and copying back, or using `std::ort` with appropriate iterators if available. Logical Error: Ensure the comparison function returns `true` if the first argument should come before the second, `false` otherwise, and adheres to strict weak ordering rules.