Re: st: A faster way to gsort

[Clyde Schechter <clyde.schechter@gmail.com>]

Joe Canner mused about the conjecture that any sort algorithm would
work faster if the data are already sorted, or nearly so.

That is probably true of most sort algorithms that are actually used
in production software.  But it is not true of all sort algorithms.

In particular, one possible sort algorithm is to read the data
sequentially unto an unbalanced binary branching tree, and then read
them out in sorted order.  This algorithm has the astonishing (to me,
at least) property that its expected performance is O(n log n), but,
if the data are already sorted, its performance is O(n^2).  In fact,
an already sorted data set is this algorithm's worst case scenario.

I don't think this approach to sorting is actually used in any
databases or statistical packages.  But it's an interesting curiosity.

Clyde Schechter
Department of Family & Social Medicine
Albert Einstein College of Medicine
Bronx, NY, USA
*
*   For searches and help try:
*   http://www.stata.com/help.cgi?search
*   http://www.stata.com/support/faqs/resources/statalist-faq/
*   http://www.ats.ucla.edu/stat/stata/