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)