Re: table.sort: invalid order function for sorting

Just take the basic common example of multikeyed sort (e.g. sorting tables
in multiple passes: you first sort by the secondary column, then sort by
the primary column; in that case when performing the second sort by the
primary column, all rows that have the same value in the premiary column
will be in reverse order (when looking at the seconday columns), even when
using a stable sort algorithm on each pass.
That's why the usual comparator for *stable* sort algorithms make the
distinction for equal keys.
The only alternative is to use a single-pass multikey sort.

But in all cases, a table which is ALREADY sorted (according to the
comparator) will shuffle rows (possibly randomly) having equal sort keys.
And this is not even optimal: the sort algorithm should not decide to swap
rows that have equal sort keys (but that's what it will do when the
comparator can only return two values). You need another algorithm which
makes the distinction of equal keys. That's not what table.sort() does, so
you need to rewrite another sort function and cannot use the builtin sort
function for very common cases.

A solution would be that table.sort can remain compatible, if it accepts
not just a boolean return value but also a signed numeric value (true means
"<=", negative means "<", zero means "=", false or positive means ">"). And
it will then be recommended for the comparator to return signed numeric
values and not booleans, it will be required if you want the builtin
table.sort to implement a stable sort; the default comparator should return
signed values)...

Le lun. 27 avr. 2026 à 15:43, 'Lars Müller' via lua-l <
[email protected]> a écrit :

> Yes, I know that Lua went with the "<" convention, so "<=" is a problem.
>
> Maybe I'm misunderstanding Philippe's point, but I don't see how "a <= b"
> would be a "good" comparator while "a < b" would be a "bad" comparator if
> one can easily be turned into the other by swapping arguments and inverting
> the result.
>
> (Strictly speaking this equivalence is of course not true with
> "uncomparable" items like NaN, but (1) once again this is intentional, and
> (2) I don't see why <= would be preferable. And "uncomparability" can still
> be tested in the same way, by checking whether both a <= b and b <= a resp.
> a < b and b < a are false.)
>
> - Lars
>
>
> On Mon, Apr 27 2026 at 00:33:11 +02:00:00, 'Martin Eden' via lua-l <
> [email protected]> wrote:
>
> On 2026-04-26 21:32, 'Lars Müller' via lua-l wrote:
>
> How so? There is no meaningful difference between "a < b" and "a <= b" as
> convention for a comparator, because "a <= b" is equivalent to "not (b <
> a)". It is just a convention, and a pretty reasonable one at that. - Lars
> That's the original issue of this thread.
>
>   Lua 5.3.6  Copyright (C) 1994-2020 Lua.org, PUC-Rio   > table.sort({ 1,
> 2, 3, 1 }, function(a, b) return not (a > b) end)   stdin:1: invalid order
> function for sorting   stack traceback:     [C]: in function 'table.sort'
>   stdin:1: in main chunk     [C]: in ?
>
> You can't have (a <= b) comparator in table.sort().
>
> On Sun, Apr 26 2026 at 13:18:38 +02:00:00, Philippe Verdy <
> [email protected]> wrote:
>
> If you want stability, suitable for mitlkey sort, or sorts in multiple
> passes, and the minimum of swaps for duplicate values, or for NaN values),
> using the comparator (a<b) does not work at all, but (a<=b) does. Lua made
> the worst decision for its binary comparator used in table.sort!
>
> Many recursive sorts are not stable. So you have to use multi-tier
> comparator because you can't afford multiple passes as in BucketSort. I am
> more saddened about random run-time explosive effect of this error. Your
> program may pass your tests but still explode in a wild. -- Martin
> --
> You received this message because you are subscribed to the Google Groups
> "lua-l" group. To unsubscribe from this group and stop receiving emails
> from it, send an email to [email protected]. To view
> this discussion visit
> https://groups.google.com/d/msgid/lua-l/90534326-894a-4993-97b4-b6d4ad80e291%40disroot.org.
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "lua-l" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected].
> To view this discussion visit
> https://groups.google.com/d/msgid/lua-l/8SH4ET.BX96HLL8DM0Q2%40gmx.de
> <https://groups.google.com/d/msgid/lua-l/8SH4ET.BX96HLL8DM0Q2%40gmx.de?utm_medium=email&utm_source=footer>
> .
>

-- 
You received this message because you are subscribed to the Google Groups "lua-l" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
To view this discussion visit https://groups.google.com/d/msgid/lua-l/CAGa7JC2gRi_U6wofg68_tcCnXq2xDNLu_Jp-Msi10OAJp20eCA%40mail.gmail.com.