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

**Peter Dalgaard BSA
**
p.dalgaard@kubism.ku.dk

*05 Sep 1997 17:02:10 +0200*

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