Luke Hutchinson

Bits, cycles and polygons. Engine programmer at Team Bondi.

The magenta and the tiny yellow areas have n<k so are irrelevant. The orange area is faster for using the limited heap algorithm, and the black area faster for the partial heapsort. We can see that for pretty much any value of k above two, the partial heapsort algorithm wins. The behaviour in the area 2≤k≤4 and 2≤n≤25 is quite odd though!

Lets now directly look at the plot for LH(n,k) vs HS(n,k).

First up, zoomed in over a small range of k so we can see the cross over point,

```reset HS(x,y)=2*x+2*y*floor(log(x)/log(2)) +(x>=y?0:0/0) LH(x,y)=x+2*x*floor(log(y)/log(2))+2*y*floor(log(y)/log(2)) +(x>=y?0:0/0) set isosamples 50 set xlabel 'n' set ylabel 'k' set ytics ( "1" 1, "2" 2, "3" 3 ) splot [1:2000] [0:3] [0:] HS(x,y), LH(x,y)```

And now zoomed out to give a fuller picture,

```reset HS(x,y)=2*x+2*y*floor(log(x)/log(2)) +(x>=y?0:0/0) LH(x,y)=x+2*x*floor(log(y)/log(2))+2*y*floor(log(y)/log(2)) +(x>=y?0:0/0) set isosamples 100 set xlabel 'n' set ylabel 'k' splot [1:5000] [1:5000] [0:] HS(x,y), LH(x,y)```

If you have gnuplot installed, it can be instructive to enter this code so you can navigate around the plot rather than simply looking at a static image.