Re: Re: easiest way to sort a list?

*To*: mathgroup at smc.vnet.net*Subject*: [mg18416] Re: [mg18344] Re: [mg18308] easiest way to sort a list?*From*: "Wolf, Hartmut" <hwolf at debis.com>*Date*: Wed, 7 Jul 1999 00:11:11 -0400*Organization*: debis Systemhaus*References*: <199906260224.WAA14461@smc.vnet.net.> <199906301813.OAA02710@smc.vnet.net.>*Sender*: owner-wri-mathgroup at wolfram.com

Hello everone, I just sent a letter to Carl K.Woll, part of which I would like to publish to the community: Hello Carl, congratulations for your brilliant solution of "easiest way to sort a list?" At the first glance, ... I was already struck. According to my measurements, you proposed not only the fastest solution, but also the second fastest, the fastest O[n log n] version. .... The question that concerned me was, is your solution really O[n]? My preoccupation before was that O[n log n] could be the best achievable. Clearly your solution is O[n] for 'smaller' samples, but the question was, is it still O[n] for very large samples? So I did some measurements, which I'd like to show you. They are in the two attached notebooks (...not for you, unless you request it from mailto:hwolf at debis.com ) What is the interpretation of the graphs? In fact your solution is as far as I could calculate seemingly linear overall. There are interesting wiggles in it. The algorithm seems to become increasingly worse, when it makes up it's mind and "starts anew". Well I think this are the traces of Mathematica's Extendible Hashing algorithm for the symbol store. When hashing becomes more and more inefficient (due to collisions) then the store ist extended. (This conforms to my observation of memory usage with Windows NT Task Manager during the calculation, where I say periods of rapid increase of used memory and times of slower grow.) So it's this extension, which keeps your algorithm linear. .... With kind regards, your Hartmut Wolf

**References**:**Re: easiest way to sort a list?***From:*"Carl K.Woll" <carlw@fermi.phys.washington.edu>