Do sorted ranges have any special properties?

[Andrei Alexandrescu]

bearophile wrote:
> 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.

Some reliability is considerably to have than patently none especially 
when approached in a principled manner (i.e. engineered to not influence 
complexity), and I don't think the variance argument holds except for 
synthetic cases (very few searches in very large ranges). Anyway, I 
think I'll insert the checks only in the debug version.


Andrei