Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

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>