Many thanks for the code because I had drawn a complete blank on the description.

The problem with it is that (as currently implemented) it is quadratic in time:

C:\test>junk -N=100
Took 0.001339 seconds for 100 items (0.000013 per item)

C:\test>junk -N=1000
Took 0.105176 seconds for 1000 items (0.000105 per item)

C:\test>junk -N=10000
Took 11.326000 seconds for 10000 items (0.001133 per item)

C:\test>junk -N=20000
Took 46.241000 seconds for 20000 items (0.002312 per item)

C:\test>junk -N=30000
Took 105.498000 seconds for 30000 items (0.003517 per item)

C:\test>junk -N=40000
Took 186.630000 seconds for 40000 items (0.004666 per item)
[download]

That's using M as 10% of N.

Which I project means over 24 hours for a million items and 4 days for 2 million.

I appreciate that doing an insertion sort using splice can be improved upon using (say) a heap, but most of the modules implementing alternatives to perl's built-in data structures, tend to be implemented using objects wrapped over hashes or arrays, and so what you gain from a somewhat more intelligent DS, you loose from the calling overheads :(