current handling of a small recursive call uses two protocols:
the input is small if the space between the start and end runs is leq k
if the input is small, just merge all the elements
both can be improved on.
the first should be an experimentally determined function of k, probably linear - there's even an argument for reducing k as you recurse and the input gets smaller (which should be preserved somewhere). expect the best results when the input is larger than k enough that the peeking helps more than it adds pointless overheads - whether we're special casing small inputs or using dynamic k
better base cases probably exist for the latter, expect binary insertion sort or insertion sort to be good methods here (try binary insertion sort first - expect comparisons to be expensive)
Carl Friedrich's pypy code has both implementations
current handling of a small recursive call uses two protocols:
the input is small if the space between the start and end runs is leq k
if the input is small, just merge all the elements
both can be improved on.
the first should be an experimentally determined function of k, probably linear - there's even an argument for reducing k as you recurse and the input gets smaller (which should be preserved somewhere). expect the best results when the input is larger than k enough that the peeking helps more than it adds pointless overheads - whether we're special casing small inputs or using dynamic k
better base cases probably exist for the latter, expect binary insertion sort or insertion sort to be good methods here (try binary insertion sort first - expect comparisons to be expensive)
Carl Friedrich's pypy code has both implementations