[Issue 24221] Stable sort crash

[d-bugmail at puremagic.com]

https://issues.dlang.org/show_bug.cgi?id=24221

--- Comment #1 from John Colvin <john.loughran.colvin at gmail.com> ---
It seems that the timsort implementation is using some inverted predicates
(e.g. greaterEqual), perhaps it is assuming antisymmetry of the inverse? That
does not follow from antisymmetry of the original predicate, which I show
below. Of course maybe it doesn't assume it, idk :shrug:

Having finished writing the following I realise it was probably a waste of time
and not a great explanation, but I'll leave it here in case it's useful:

assuming `<` on the underlying types in antisymmetric (if, for any x != y, f(x,
y) is true, then f(y, x) will be false), then any && combination will also be.

f = (x, y) => x.a < y.a && x.b < y.b

the only way f(y, x) and f(x, y) could be true - breaking antisymmetry - would
be if both x.a < y.a && y.a < x.a && x.b < y.b && y.b < x.b, which we have
already assumed is not the case ("assuming `<` on the underlying types in
antisymmetric").

BUT, quoting phobos:

bool greaterEqual()(auto ref T a, auto ref T b) { return !less(a, b); }

so this is

(x, y) => !(x.a < y.a && x.b < y.b)

which can be rewritten as

!(x.a < y.a) || !(x.b < y.b)

and we can see that both q(x, y) and q(y, x) CAN be true, expanded it is

(!(x.a < y.a) || !(x.b < y.b)) && (!(y.a < x.a) || !(y.b < x.b))

which can be satisfied if only one || clause is true in each side of the &&, so
we can choose a clause only impacting .a for one of them and .b for the other,
avoiding contradicting the reflexivity of `<` for the underlying type.

--