Iterator::is_sorted Stops at the First Inversion

To prove that a sequence is sorted, every adjacent pair may need inspection. To prove it is not sorted, one inverted pair is enough.

The failing program checks 1, 3, 2, 4. Iterator::is_sorted sees the inversion from three to two, returns false, and leaves four unvisited.

False is available before exhaustion

The method compares successive values in nondecreasing order. Once a later value is less than its predecessor, future values cannot repair the fact that the complete sequence contains an inversion.

Short-circuiting saves work and permits a finite false answer on some unbounded sources. It also means is_sorted is not an exhaustive pass for side effects or diagnostics.

The returned boolean says enough evidence was found, not that the iterator reached its end.

Both values in the inverted pair were consumed

To observe that 3 > 2, the iterator must pull both values. The value two is the first failing item and is no longer in the remainder. Four is still next.

The repaired program borrows the iterator with by_ref, checks the result, and asserts the remaining four. This makes the state boundary executable.

If is_sorted owns the iterator directly, the owner is consumed and the caller cannot resume, though the method may still have stopped before exhaustion internally.

Finding every inversion needs another pass shape

A diagnostic tool may need all positions where ordering breaks. is_sorted returns only a boolean and stops at the first.

I keep the previous item and enumerate the source explicitly, recording every violating pair. This can be more expensive, but it fulfils a different promise.

For production validation, reporting the first inversion is often enough. I then include both values and their positions rather than only “not sorted.”

Custom comparators add policy

is_sorted_by lets callers define comparison behavior. The comparator may also short-circuit with the method.

I keep comparators pure. Logging or mutation inside them produces a prefix-dependent trace, and a comparison that is not a coherent order can make results difficult to interpret.

For floats, partial ordering and NaN need an explicit decision. Using a total comparator can define deterministic storage order, but that does not automatically mean the sequence is numerically valid.

Equal neighbors are sorted

The standard check is nondecreasing, so equal adjacent values are accepted. If the domain requires strict increase, duplicates are failures even though is_sorted returns true.

I name the rule nondecreasing or strictly_increasing. A sorted-ID validator that silently permits duplicates may later break uniqueness assumptions.

The strict form needs an explicit pair comparison or a comparator that rejects equality according to the chosen API contract.

Sorted observation does not freeze the source

Checking a snapshot or iterator does not prevent another thread or external producer from changing the underlying data later. For a borrowed slice under exclusive or immutable access, the observed region remains stable for the borrow. For databases and streams, ordering may be a query contract rather than a property proven forever.

I attach the check to the boundary where ordering is consumed, or use a type/constructor that validates and owns the sequence.

Infinite iterators can run forever on success

An infinite increasing iterator never finishes proving that every future pair is sorted. It can return false if an inversion arrives but cannot return true without a finite boundary.

For streams, I validate bounded windows or monotonic updates one at a time. The claim becomes “sorted so far,” which is temporally honest.

What I test

My table includes empty, one-item, increasing, equal-neighbor, first-inversion, middle-inversion, and final-inversion sequences. A counted iterator proves which elements were pulled.

For custom ordering I add ties, NaN or incomparable values where relevant, and tests of comparator consistency. If resumption is supported, I assert the exact next item after false.

Validation after transformation tests another sequence

Calling map(...).is_sorted() checks transformed outputs, not the original values. A lossy key function can hide inversions by mapping distinct items to the same key. This may be intended for grouping and wrong for canonical source order.

I retain original positions in diagnostics and state whether ordering is by complete value, extracted key, or normalized representation. The short-circuit boundary then refers to the sequence the product actually defines.

The core principle is that a proof query may stop as soon as one outcome becomes inevitable. is_sorted short-circuits on the first inversion, consuming that pair but not the tail. Use it for a boolean order check; use an explicit traversal when every inversion or every side effect must be observed.