bug#69709: `sort` interface improvement and universal ordering predicate

[Mattias Engdegård]

The existing `sort` interface suffers from some usability problems:

1. Writing an ordering predicate is often difficult and error-prone, even for 
very basic tasks such as selecting the field to sort on. It's not uncommon to 
botch a predicate as simple as

  (lambda (a b) (< (f a) (f b)))

which I've managed to do myself more than once. It gets particularly messy when 
sorting on multiple fields.
Having to write a custom comparison function for almost every occasion also 
means that performance suffers.

2. Mutability by default is a bug magnet as well.

To deal with the first problem, we could:

* Add a universal ordering predicate that will compare two values of the same 
type for many built-in types: numbers, strings, symbols, markers, lists, 
vectors, records, and a few more.
* Make this ordering the default.
* Add a key (accessor) function argument, like that in the recent `sort-on` 
interface, but built-in. This is important.

These work very well together: the user does not need to write or even choose 
an ordering predicate in most cases. Key functions are much less error-prone to 
write, and with the lexicographic ordering of lists, vectors and records, 
multi-key sorting is made much easier.

A key function combined with a standard ordering can also be used to optimise 
comparisons since we have all key values up front along with how they should be 
compared. The original timsort code that we stole from Python did this.

As a starting point, a patch implementing a universal ordering predicate is 
attached below.

The proposed sorting function interface would be

  (new-sort seq &key key lessp destructive)

because the keyword interface is easier to read and write than a lengthening 
list of optional positional parameters, and can be extended more gracefully. 
For example, it could be handy to have a `reversed` (or `descending`) 
parameter. The parsing cost is not significant.

Instead of inventing a new and rather meaningless function name, I suggest we 
re-use `sort` and allow both

  (sort seq lessp)                       ; old-style
  (sort seq &key key lessp destructive)  ; new-style

since they are easy to distinguish, and let `destructive` default to false in 
new-style calls, true in the old style.

0001-value-less-p.patch
Description: Binary data