http://www.perlmonks.org?node_id=599632


in reply to Re^7: Perl is dying (better sorting than the ST)
in thread Perl is dying

it appears to me that with an ST you have N steps to create the arrays, and N steps to unpack them, with your code you have N steps to create the key array, and N steps to map the sorted keys back to real values.

I was talking about memory, not efficiency. Even if Perl had tuples, ST still requires extra memory for container structures proportional to the size of the list being sorted, whereas index sorting only requires a single container. Although in terms of big-O, that’s irrelevant, since if you consider the keys as well, then the ST requires extra memory on the order of n · (s + a) (where s and a are constants and stand for the overhead of a scalar and array, respectively) whereas index sorting only requires n · s + 1 · a; but these are both O(n).

My bad.

Of course, in Perl, there’s a huge difference between the two because n · a easily becomes a considerable quantity.

However, I don’t see how index sorting is a premature optimisation. It’s not just parsimonious with memory, it’s also easier to follow (in my opinion) than the ST for someone who has never seen either idiom.

The real way to go about making sorting faster would of course be to decouple key extraction from the comparator function, which would allow almost all sorts to be written declaratively. There was discussion about this on perl6-language back when I was subscribed, but I don’t know if anything came of it.

Makeshifts last the longest.