Re: cl.el sort* efficiency

[Stefan Monnier]

> I don't know how representative I am, but it's pretty obvious to me that
> adding something like :key to sort might call the given function
> multiple times.  Certainly the alternative of allocating storage to keep
> around all retrieved key values is pretty heavyweight and in many cases
> not an optimization at all, so it's not something I would expect an
> implementation to do.

Actually, I do believe that when I was a CL user I expected that the sort
function would call the :key function only O(n) times rather than O(n log n)
times.  If I didn't want the allocation of an aux table I used something
like car-less-then-car for the comparison function.


        Stefan