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