R-alpha: Sorting Efficiency -- thoughts.. : if(!is.sorted(x)) x <- sort(x)

[Peter Dalgaard BSA]

Martin Maechler <maechler@stat.math.ethz.ch> writes:

> since
> 1.	        is.sorted  is  O(n)
>     whereas	sort       is  O(n*log(n)) 
> 2. for sorted x, the two assignments are superfluous even when order(x) was
>    very fast (for SORTED x). 

Actually, if it's a Shell sort, it's O(n^1.5) worst case and O(n^1.27)
average. For O(n log n) average you need quicksort or heapsort. The
former has the draw back of O(n^2) worst case, but heapsort has quite
a good reputation and is unconditionally n log n (that info comes from
Numerical Recipes, which was the best could dig out at the moment).
Maybe we should switch?

> superfluous, but the situation with order(.) above
> (which is NOT infrequent in statistics !!) would still profit from not
> doing  'x <- x[1:length(x)]' when x is sorted.

Yes.. Of course the case is often that you *know* that things are
sorted (because you just did it yourself), but modularity prevents you
from getting that information to the spot where it is needed.

-- 
   O__  ---- Peter Dalgaard             Blegdamsvej 3  
  c/ /'_ --- Dept. of Biostatistics     2200 Cph. N   
 (*) \(*) -- University of Copenhagen   Denmark      Ph: (+45) 35327918
~~~~~~~~~~ - (p.dalgaard@biostat.ku.dk)             FAX: (+45) 35327907
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
r-devel mailing list -- Read http://www.ci.tuwien.ac.at/~hornik/R/R-FAQ.html
Send "info", "help", or "[un]subscribe"
(in the "body", not the subject !)  To: r-devel-request@stat.math.ethz.ch
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-