Re: table.sort: invalid order function for sorting

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.