R-alpha: Sorting Efficiency -- thoughts.. : if(!is.sorted(x)) x <- sort(x)
Fri, 5 Sep 1997 10:40:42 -0500 (CDT)
Peter Dalgaard BSA wrote:
> Martin Maechler <email@example.com> 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).
University of Minnesota Phone: 612-625-7843
School of Statistics Fax: 612-624-8868
206 Church Street email: firstname.lastname@example.org
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: email@example.com