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

[Luke Tierney]

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