Re: master 4b79c80c999 1/2: New function 'sort-on'

[Yuri Khan]

On Mon, 5 Feb 2024 at 07:49, Dmitry Gutov <dmitry@gutov.dev> wrote:

> The result would make it destructive and consequently faster (not
> entirely non-consing, but close to it--while the current sort-on creates
> two extra lists of length N), which should fit the original goal: a
> faster sorting routine then uses ACCESSOR.

Schwartzian transform transforms a sort algorithm that is O(n log n)
accessor calls + O(n log n) comparison calls into one that is O(n)
accessor calls + O(n log n) comparison calls. Depending on the
accessor expensiveness, that may or may not balance out the consing
and eventual GC.