Re: table.sort: invalid order function for sorting

Note that if you don't want to change this  builtin   table.sort behavior,
there are alternatives:
- use an extra parameter (after the compartor) stating that you want a
stable sort (in that case the builtin "fast" sort algorithm (suitable for
sorting tables with no duplicate keys, whereas it can still handle NaN
numeric values specially in the builtin comparator, so that they all sort
consistanently either after or before other numeric values) will be
replaced by a stable sort algorithm (which may be a bit slower).
- use another function for "table.stablesort", taking a comparator
returning a signed number, such as (a-b) if a and b are both numeric (and
there's no overflow for the result of the substraction itself when
comparing values with high magnitudes but opposite signs), where only the
sign of that comparison matters.
The common C/C++ libraries implementing sorting use a comparator returning
a signed value, not a boolean, allowing stable sorting implementations (in
those libraries you may choose the sort algorithm to use, or there may be
some builtin thresholds of table size where an algorithm may be prefered to
another, such as bubble sort for very small tables, or merge sorts using
external stores and caches for very large tables, and common "quicksort"
for intermediate sizes).

Le dim. 3 mai 2026 à 21:01, Philippe Verdy <[email protected]> a écrit :

> 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/CAGa7JC0mXRi__%2BLNACthGj1%2BSizPjijhd%2B4-Y3OuCqPrTQD3-g%40mail.gmail.com.