D2's std.algorithm and sorting

[bearophile]

Bill Baxter:
> sort!("a > b")(array);
> I just wanted to say that this is BRILLIANT!  Zero call overhead,
> zero syntax overhead, compile-time lambda functions!

Sorry for raising this thread again (with a different name) after so much time, I want to say something that comes from my experience.
Python list.sort()/sorted(iterable) accepts an optional cmp() function too, but later they have added the "key" optional parameter too, and today most of the times you use key instead of cmp.

http://docs.python.org/lib/typesseq-mutable.html

key specifies a function of one argument that is used to extract a comparison key from each list element, like key=str.lower.

An example:
>>> l = [7,2,2,-10,10,-10,-3,4,-9,-7]
>>> sorted(l)
[-10, -10, -9, -7, -3, 2, 2, 4, 7, 10]
>>> l.sort(key=abs)
>>> l
[2, 2, -3, 4, 7, -7, -9, -10, 10, -10]

Using key requires more memory (for the "decorated" elements), but it's often much simpler to use.
A good sorting routine has many conflicting goals:
- easy to use with a short and simple syntax, for 99% of situations where you have a small array and you both don't need max sorting speed nor to use as little memory as possible.
- very fast and memory-lean when used on LOT of data.
- able to sort really fast already partially sorted arrays.
- etc.

The key() parameter is useful for the first situation, that is very common. For all the other situations you can accept a more fussy syntax, that allows you to use less memory and/or to sort faster. So I think the "a > b" idea is cute and useful where you need to save memory, but in many easy situations a key function as parameter is better (simpler to use).
(I have developed a large library of D function/classes, mostly for functional-style programming (but useful for other things too), it has both a much faster sort than the built-in one, and a sort/sorted functions (for arrays and AAs, iterable classes, etc) that accept an optional key() function too. Maybe such stuff may be useful for Phobos/Tango).

Bye,
bearophile