Do sorted ranges have any special properties?

[bearophile]

Andrei Alexandrescu:
> (I also have a cool 
> idea for statistically checking sortedness without deteriorating 
> complexity. Essentially assumeSorted(r) could check that r is sorted by 
> tossing a rigged coin with P(head)=1.0/r.length and deciding to check if 
> head comes up. That way, the amortized complexity of the check is O(1)).

But the safety (reliability) of such test is low, and it can increase a lot the variance of the running time of a piece of code... So it's a cute idea, but I am not sure it's a good one.

Bye,
bearophile