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

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
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-