Re: avoid narrow-to-region (was: Re: replace-regexp)

[Yuri Khan <yuri.v.khan@gmail.com>]

On Sun, 9 May 2021 at 06:00, Emanuel Berg via Users list for the GNU
Emacs text editor <help-gnu-emacs@gnu.org> wrote:

>       (sort-subr nil
>                  #'forward-line
>                  #'end-of-line
>                  nil nil
>                  (lambda (_ __) (zerop (random 2)) )))))

Note that this is not a suitable sorting predicate. It violates all
axioms of a strict weak ordering:

* Consistency: If (f a b) returns t once, it must return t when called
again with the same arguments.
* Irreflexivity: (f a a) must return nil. Your predicate returns nil
or t randomly.
* Antisymmetry: of (f a b) and (f b a), no more than one may return t.
In your case, both can return t.
* Transitivity: If (f a b) and (f b c) both return t, (f a c) must
also return t.
* Transitivity of equivalence: if (f a b), (f b a), (f b c), (f c b)
all return nil, then (f a c) and (f c a) must also return nil.

Generic sorting algorithms typically require the predicate to conform
to all of the above; otherwise, they may signal an error or enter an
endless loop.

I have not analyzed whether ‘sort-subr’ has any issues with
inconsistent orderings, and its docstring does not mention these
requirements, but it would be a good idea to avoid that anyway.

Also, using a sorting algorithm to randomize an ordered sequence is a
bit of an overkill. Sorting has an asymptotic complexity of O(n log
n), but the Fisher–Yates–Durstenfeld shuffle algorithm is O(n).

https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle