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

[Dmitry Gutov <dmitry@gutov.dev>]

On 23/03/2024 22:09, Stefan Monnier wrote:
>> So others will have to go around each such project, ensure the original list
>> is "owned" and add the :in-place argument, to reach the optimum
>> performance. That's why, I think, 'sort' is mutating in most languages.
> I think it's mutating in "most languages" because "most languages" are
> imperative and because those primitives usually operate on arrays (a
> "naturally imperative" data structure) rather than on singly-linked
> lists (a "naturally more immutable" data structure).

There aren't many general purpose languages around which use cons cells 
and have 'sort' in stdlib for them, to compare.

To get back to the example of Clojure, which touts immutability most of 
the time, the 'sort' routine first copies a sequence into an array 
(apparently for performance - fewer indirections and better locality 
when subsequently swapping values around), and then returns that array 
with a thin wrapper called ArraySeq (which it 1 extra object, not N).

https://github.com/clojure/clojure/blob/ce55092f2b2f5481d25cff6205470c1335760ef6/src/clj/clojure/core.clj#L3103-L3118

IIUC we allocate an array internally as well during the sorting phrase, 
but then we can't return it as-is or with a thin wrapper (if only 
because the user expects back a list, not a vector), so we'll need to 
allocate a whole new list to avoid mutating the original. And our GC is 
worse than JVM's.