Miles Bader writes: > > 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, I see your point, I guess there's two equally good features (an accessor or a preprocessor), it's just a matter of which one is offered. Stefan Monnier writes: > > 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. At least I'm not the only one who thought in that direction :) "Juanma Barranquero" writes: > > Of course. I didn't meant that the idea was invented by Randal > Schwartz, or recently; but it's very popular under that name. No, confusion only on my part. Not that the wiki article is fantastically clear on concept versus the idiom (it's all there, but rather laboured). Without wanting to labour this sort* either :), I'd like to propose a further tweak to the documentation. In fact I think it's enough to leave the code alone and just make it a little clearer what one gets. 2006-12-26 Kevin Ryde * cl.texi (Sorting Sequences): In sort*, don't say "preprocess" as that suggests O(N) :key use. Show structs as an example, since downcase is more expensive than intended for the :key func. Another tweak to the wording of :key only an accessor. For ease of reading: -- Function: sort* seq predicate &key :key This function sorts SEQ into increasing order as determined by using PREDICATE to compare pairs of elements. PREDICATE should return true (non-`nil') if and only if its first argument is less than (not equal to) its second argument. For example, `<' and `string-lessp' are suitable predicate functions for sorting numbers and strings, respectively; `>' would sort numbers into decreasing rather than increasing order. This function differs from Emacs' built-in `sort' in that it can operate on any type of sequence, not just lists. Also, it accepts a `:key' argument which is used to access part of an element for the PREDICATE function. For example, to sort structures by a particular field (*note Structures::) (defstruct person name age sex) (setq data (sort* data 'string-lessp :key 'person-name)) Or `car' would be useful for sorting association lists. The `:key' function is designed only as a data accessor though, it's used on every predicate call. The `sort*' function is destructive; it sorts lists by actually rearranging the `cdr' pointers in suitable fashion.