Re: table.sort: invalid order function for sorting

Sort algorithms assume that when compariing pairs of items, if this
comparison return true, then the two items dont need to be swapped; if this
comparison returns false, the two items are swapped unconditionally.
Normally also the two compared temps a and b are where where the index of
item "a" in the table is LOWER than the index of item "b".

Now take the case of a table which is ALREADY COMPLETELY SORTED.
- Take the extreme case where all items in the table are equal to each
other: the sort function wll compare items using that function that returns
false for EVERY compared pair, so the algorithm will always swap items,
everywhere. This makes the sort function VERY UNSTABLE
- Take another extreme case where all items in the table are NaN floatting
number: the sort function will compare items using that function that also
return false for EVERY compared pair, so the algorithms will also always
swap items.

Lua has used a very uncommon definition of a generic table sort algorithm
which will NEVER be stable, and will be unnecessarily very slow/inefficient
(for tables that are already sorted but contain duplicate values or NaN
values), because its compare function is (a < b) with a strict comparison,
instead of the usual (a <= b) with a non-strict comparison!

This absence of basic stability is that you CANNOT use table sort() in
successive times (but using different column subitems) to perform a
multi-keyed sort (where duplicate values are expected, notably for the
primary sort key which is the last key used to sort the table), as
secondary (or tertiary) keys that were first sorted will be SHUFFLED when
sorting by the primary key.

This is a severe design bug for table.sort()!



Le ven. 17 avr. 2026 à 16:22, Francisco Olarte <[email protected]> a
écrit :

>
> On Fri, 17 Apr 2026 at 15:55, 'Sewbacca' via lua-l <[email protected]>
> wrote:
>
>> Would it be possible to make table.sort stable via this trick?
>>
>> local t = ...
>> local orig = {}
>> for i,v in ipairs(t) do orig[v] = i end
>> table.sort(t, function(a, b)
>>     if a == b then return orig[a] < orig[b] end
>>     return a < b
>> end)
>>
>> assume t is a table of objects with valid __le and __eq meta fields.
>>
>
> Normally it is easier to define _lt, but I think lua DTRT ( a<b => not
> b>=a )
>
> It should work, if ( I am not sure but IIRC it does ) objects are
> different as table keys.
>
> Another thing you can try is a Swartchzian transform, remap the table to {
> obj, index }, sort lexicographically, undo the map. This has the
> disadvantage of trading the new "big" table for a lot of small ones, but it
> may be interesting.
>
>  > I suspect for large n that the runtime wouldn't be particularily good.
>
> It does not put extra complexity, sort is normally O(N*logN) and the
> copies should be O(N). Comming from C++ where less is heavily use I would
> prefer to just define _lt and knowing ( _eq(a,b) can be expressed as not
> (_ly(a,b) or _lt(b,a)) use something like this for comparing:
>
> return  (a<b) -- directly less
>         or not ( a>b or orig[a]>orig[b]) -- if a>b it is not less, else a
> must be == use orig.
>
> (blood caffeine level is too low, but I think it is correct ).
>
> Francisco Olarte.
>
> --
> 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/CA%2BbJJbxnrtdZ5YYX%3DDOEk_NsXxCLeef7Car4S9MirEfzVx36bw%40mail.gmail.com
> <https://groups.google.com/d/msgid/lua-l/CA%2BbJJbxnrtdZ5YYX%3DDOEk_NsXxCLeef7Car4S9MirEfzVx36bw%40mail.gmail.com?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/CAGa7JC3KZDecK_0dP_36FBgPu%3DN4YbArLisfOUsJh2Tgd%2BzAXg%40mail.gmail.com.