Heapsort

Stephen Weeks MLton@sourcelight.com
Wed, 20 Jun 2001 16:45:59 -0700


> I can only conclude that something is really wrong with our generated code on
> the heapsort.  If you look  at  the  graph  from  the  programming  languages
> shootout  page,  you will see that we are about 4 times slower than OCaml, so
> even with the new compiler we will be half the speed.  Also if  you  look  at
> the  graph,  we  are even worse than SML/NJ, and the slope (time vs. size) is
> worse.

I would say < 3.5, but OK.  As to the slope, heapsort is n log n, so what I
think MLton's being higher means is that we are faster on the linear part of
creating the array, but slower on the n log n part of sorting the array.  Bad.