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

**Luke Tierney
**
luke@stat.umn.edu

*Fri, 5 Sep 1997 10:40:42 -0500 (CDT)*

Peter Dalgaard BSA wrote:
>*
*>* 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?
*>*
*
Merge sort is also an option. It is O(n log(n)) worst case but with a
better constant than heapsort, as I recall, and a bit easier to
implement. Its drawback in general is O(n) additional space needed,
which is prohibitive if you are sorting in place. But since R copies
anyway, that isn't an issue. (Don't name any internal routines
mergesort though -- there are a number of systems that include one in
their libraries and cause name conflicts).
luke
--
Luke Tierney
University of Minnesota Phone: 612-625-7843
School of Statistics Fax: 612-624-8868
206 Church Street email: luke@stat.umn.edu
Minneapolis, MN 55455 USA WWW: http://www.stat.umn.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
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
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-