How to Sorting in C++ Standard Template Library (STL)

Use the C++ standard library’s sort() function from <algorithm> to order an array or vector in place. By default, it sorts the half-open range from first up to, but not including, last in ascending order. Pass a comparator to choose another ordering.

Use the sort() Function to Sort an Array or Vector in C++

std::sort accepts random-access iterators, so it works with arrays and vectors. It cannot reorder std::set or std::map in place because those containers do not provide random-access iterators. This complete program sorts both an array and a vector:

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

int main() {
    int values[] = {8, 3, 6, 1, 5};
    std::vector<int> scores{14, 7, 22, 9};

    std::sort(std::begin(values), std::end(values));
    std::sort(scores.begin(), scores.end());

    for (int value : values) std::cout << value << ' ';
    std::cout << '\n';
    for (int score : scores) std::cout << score << ' ';
    std::cout << '\n';
    return 0;
}

std::begin and std::end provide the array’s range, while the vector uses its begin() and end() iterators. This program is provided as an unexecuted example; its output is omitted until it is observed in the configured runtime. Both calls modify the original elements, so later code sees them in the new order. To sort only part of a container, pass iterators delimiting that portion.

Sort an Array or Vector in Descending Order in C++

Pass std::greater<> as the third argument to order values from greatest to least. Include <functional> for the comparator. For example, std::sort(values.begin(), values.end(), std::greater<>{}); sorts a vector in descending order. The comparator changes the ordering rule without changing which range is sorted.

Use partial_sort() to Sort Part of an Array or Vector

Use partial_sort(first, middle, last) when only a prefix must be ordered. It places the smallest middle - first elements in sorted order before middle. The elements from middle to last are not guaranteed to have any particular order. For example, std::partial_sort(values.begin(), values.begin() + 3, values.end()); selects the three smallest values for the first three positions.

Use a Custom Comparator with sort() in C++

A comparator lets you order values by a key such as string length. For example, std::sort(words.begin(), words.end(), [](const std::string& a, const std::string& b) { return a.size() < b.size(); }); places shorter strings first. A comparator must define a strict weak ordering: it must be consistent and must not consider an item to precede itself. Strings with equal lengths are equivalent under this comparison, so their relative order is unspecified. Include <string> along with <algorithm> when using this example.

Check Whether a Range Is Sorted with is_sorted()

std::is_sorted(first, last) returns true when the range from first up to, but not including, last is ordered according to the default comparison, and false otherwise. It checks the range without rearranging its elements. Supply the same comparator used for a custom ordering when checking that ordering, as in std::is_sorted(words.begin(), words.end(), compare).

Time Complexity of Sorting Algorithms

For std::sort, the standard specifies O(N log N) comparisons in the worst case, where N is the number of elements in the range. This describes how the work grows with the range length; it does not promise a particular sorting implementation. std::partial_sort uses approximately N log K comparisons when selecting and ordering K elements from N, while std::is_sorted makes at most N - 1 comparisons. These bounds help distinguish fully sorting a range from ordering only a prefix or checking an existing order.