C++ Basics: Locate the First Broken Sort Order

Use std::is_sorted_until to report where a nondecreasing sequence first stops being sorted.

Prepare a scratch directory

Tested on Linux x86_64 with GCC 14.2.0. Install a C++20-capable compiler and standard-library development headers, with g++ on PATH. You also need Bash, a text editor, and the mktemp, rm, and rmdir utilities. No third-party library is required.

Keep the same terminal open. Stop if setup fails, before saving the source:

start_directory="$PWD"
work_directory="$(mktemp -d)" || exit 1
cd -- "$work_directory" || exit 1

Run the example

Save this as is-sorted-until-diagnostic-demo.cpp:

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

int main()
{
    const std::vector<int> values{2, 4, 4, 3, 8};
    const auto broken = std::is_sorted_until(values.begin(), values.end());
    if (broken == values.end()) {
        std::cout << "Sorted\n";
    } else {
        std::cout << "First unsorted index: " << std::distance(values.begin(), broken) << '\n';
        std::cout << "Pair: " << *std::prev(broken) << " -> " << *broken << '\n';
    }
}

Compile and run it. The program runs only after compilation succeeds:

g++ -std=c++20 -Wall -Wextra -Werror -pedantic is-sorted-until-diagnostic-demo.cpp -o is-sorted-until-diagnostic-demo &&
./is-sorted-until-diagnostic-demo

Observed output:

First unsorted index: 3
Pair: 4 -> 3

Read the result

The prefix 2, 4, 4 is sorted. The next element, 3, breaks the ordering and produces index 3. Equal neighboring values are accepted by the default nondecreasing ordering. The input is inspected without mutation.

Apply it carefully

For this algorithm, a non-end failure result cannot be begin(), so prev(broken) is valid after the end check. Empty and one-element inputs are already sorted. The function diagnoses the first violation; it does not identify every misplaced value or repair the sequence. When checking descending data, pass the same comparator used to establish that order.

The C++ working draft describes the relevant rules. This example builds in C++20 mode; the current working draft also documents later additions.

Clean up

Remove only the source and executable created here, then return to the starting directory:

rm -- is-sorted-until-diagnostic-demo.cpp is-sorted-until-diagnostic-demo
cd -- "$start_directory" || exit 1
rmdir -- "$work_directory"
unset start_directory work_directory

If the directory is not empty, inspect its remaining contents before removing anything else.

Acknowledgements

This post was created with assistance from AI.