std::is_sorted

Use case

Check if range is sorted.

Explanation

std::is_sorted_until returns iterator to first out-of-order element. Useful for validation before using algorithms that require sorted input (e.g. std::binary_search).

Time complexity: O(n) worst case but short-circuits at first out-of-order element. See possible implementation.

Code

#include <algorithm>
#include <cstdint>
#include <print>
#include <vector>

int main() {
  std::vector<uint64_t> good = {0x1000, 0x2000, 0x3000, 0x4000};
  std::vector<uint64_t> bad = {0x1000, 0x3000, 0x2000, 0x4000};

  std::println("good sorted: {}", std::is_sorted(good.begin(), good.end()));
  std::println("bad sorted: {}", std::is_sorted(bad.begin(), bad.end()));

  auto it = std::is_sorted_until(bad.begin(), bad.end());

  if (it != bad.end()) {
    size_t offset = std::distance(bad.begin(), it);
    std::println("Sorting breaks at {:#x} (index {})", *it, offset);
  }

  return 0;
}

View on GitHub.

Output

$ ./src/algorithms/build/std-is_sorted
good sorted: true
bad sorted: false
Sorting breaks at 0x2000 (index 2)