table.sort: invalid order function for sorting

[Martin Eden]

Hello guys,

I've just found unobvious thing about table.sort:

  -- ! invalid order function for sorting
  table.sort({ 1, 2, 3, 1 }, function(a, b) return (a <= b) end)

Lua manual says:

  The comp function must define a consistent order; more formally, the
  function must define a strict weak order. (A weak order is similar to
  a total order, but it can equate different elements for comparison
  purposes.)

and for me <= operator is weak order.


Practically it means that table.sort() never passes same item
to comparator and when writing comparisons explicitly,
default is "false":

local compare =
  function(a, b)
    if (a < b) then return true end
    if (a > b) then return false end

    return false
  end


This error is not stable for my use case with comparing tables.
"return false" default eliminates it but sometimes "return true"
works too.

Bug?


-- Martin

[Spar]

This is not strict weak order because it lacks irreflexivity. a < a returns false, but yours returns true.

Table.sort doesn't compare the same object with itself, but it can definitely compare two identical values in the array if they are present multiple times

--
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 lua-l+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/lua-l/990cd9ac-fdb2-4d05-acac-128559523984%40disroot.org.

[Halalaluyafail3]

On Friday, April 17, 2026 at 8:55:59 AM UTC-4 Martin Eden wrote:

Hello guys,

I've just found unobvious thing about table.sort:

  -- ! invalid order function for sorting
  table.sort({ 1, 2, 3, 1 }, function(a, b) return (a <= b) end)

Lua manual says:

  The comp function must define a consistent order; more formally, the
  function must define a strict weak order. (A weak order is similar to
  a total order, but it can equate different elements for comparison
  purposes.)

and for me <= operator is weak order.

The usual definition of strict weak orders does not permit this. In particular the comparison function should be irreflexive (f(x,x) is always false), asymmetric (f(x,y) being true implies f(y,x) is false), transitive (f(x,y) being true and f(y,z) being true implies f(x,z) is true), and transitive for values that compare equal (all of f(x,y), f(y,x), f(y,z), and f(z,y) being false implies f(x,z) and f(z,x) are both false). The comparison function here is reflexive (ignoring NaN) and not asymmetric, so it is not valid.
 

Practically it means that table.sort() never passes same item
to comparator and when writing comparisons explicitly,
default is "false":

local compare =
  function(a, b)
    if (a < b) then return true end
    if (a > b) then return false end

    return false
  end

return a<b
 

This error is not stable for my use case with comparing tables.
"return false" default eliminates it but sometimes "return true"
works too.

Bug?

I do not see a bug here. Though it will not always diagnose a bad ordering.
 

-- Martin

[Sewbacca]

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.

I suspect for large n that the runtime wouldn't be particularily good.

[Francisco Olarte]

On Fri, 17 Apr 2026 at 15:55, 'Sewbacca' via lua-l <lu...@googlegroups.com> 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.

[Philippe Verdy]

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()!

--
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 lua-l+un...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/lua-l/CA%2BbJJbxnrtdZ5YYX%3DDOEk_NsXxCLeef7Car4S9MirEfzVx36bw%40mail.gmail.com.

[Martin Eden]

Nice examples, Philippe

I've thought about current Lua's approach. Requiring strict ordering
(with inherited irreflection) makes some sense if we want to minimize
number of calls of comparison function.

But for me it's schizophrenic: trying to fit tertiary value into binary.
For me linear order comparison has three values: less, equal, greater.
You can't fit them into boolean and build sorting algorithm on that
without discovered side effects.

If someone wants to use boolean comparators - he still needs two of them.
For example is_less() and is_equal(). Of course I won't be happy
to provide two almost identical blocks of code for them.

For me requirement of comparison function to return one of three values
is more natural and acceptable than providing fragile sorting algorithm
for binary comparator.

You can't even easily invert sorting like:

-- Ascending sort
table.sort(Orders, function(a, b) return DateIsLess(a, b) end)

-- Descending sort? Nah! Wandering runtime error!
table.sort(Orders, function(a, b) return not DateIsLess(a, b) end)

-- Martin

[Lars Müller]

You can easily invert sorting. You just swap the two arguments:

table.sort(Orders, function(a, b) return DateIsLess(b, a) end)

Also not sure I get your point about needing to implement both "less than" and "is equal".
"Less than" suffices, you can default "is equal" to "not (lt(a, b) or lt(b, a))".

Needing two "comparator" calls to decide equality may of course not be ideal for runtime,
but tends to be fine since it usually just adds a constant factor of about ~2 at worst.

I think having comparators be boolean "less than" functions makes some sense though.
I want to be able to just write something like table.sort(t, function(a, b) return a > b end).

Introducing a kind of "spaceship operator" seems like too much for a simple scripting language like Lua.
What would the type of the result be? You could make it a number, of course, but that's really a hack.
(And one that tends to produce bugs when you have integer wraparound, which Lua does.)
I prefer the boolean-typed result of a "less than" comparison.
(I contemplated "lt(a, b)" evaluating to nil if they a == b as a convention for comparators,
which would mostly still keep things working as nil is falsey, but that's also hacky.)

- Lars

--

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 lua-l+un...@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/lua-l/a832ad81-b9e5-47ac-af82-48c666412809%40disroot.org.

[Martin Eden]

On 2026-04-24 17:28, 'Lars Müller' via lua-l wrote:
> You can easily invert sorting. You just swap the two arguments:
>
> table.sort(Orders, function(a, b) return DateIsLess(b, a) end)

That's right. Came to that after 40 seconds since I sent email.

But we can't say it's obvious, right? Besides, in real life there will
be several lines of code instead of "a, b".

> Also not sure I get your point about needing to implement both "less
> than" and "is equal".
> "Less than" suffices, you can default "is equal" to "not (lt(a, b) or
> lt(b, a))".
>
> Needing two "comparator" calls to decide equality may of course not be
> ideal for runtime,
> but tends to be fine since it usually just adds a constant factor of
> about ~2 at worst.

Time spent in comparator is not limited. So sorting time may consist
mostly of time in that function. Imagine we're doing web request for
each comparison.. Imagine two times longer line of people in every
shop you visit..

> I think having comparators be boolean "less than" functions makes some
> sense though.
> I want to be able to just write something like table.sort(t,
> function(a, b) return a > b end).
>
> Introducing a kind of "spaceship operator" seems like too much for a
> simple scripting language like Lua.
> What would the type of the result be? You could make it a number, of
> course, but that's really a hack.
> (And one that tends to produce bugs when you have integer wraparound,
> which Lua does.)
> I prefer the boolean-typed result of a "less than" comparison.
> (I contemplated "lt(a, b)" evaluating to nil if they a == b as a
> convention for comparators,
> which would mostly still keep things working as nil is falsey, but
> that's also hacky.)

Yeah it's hacky. But I agree that we need some three-ways binary
operator for
scalar comparisons.

Boolean "less than" is perfectly fine. Problem that comparisons are costly.
So we spent like 24800 microseconds just to get data. And then
compare numbers and return 0 or 1. Which takes like 20 micros.

Ideally comparator should provide as much information about relation of
given items as it can. At least three output values if there is linear
order.
What sorting algorithm will do with them is his own business.

>
> - Lars

-- Martin

[Francisco Olarte]

On Fri, 24 Apr 2026 at 16:52, 'Martin Eden' via lua-l <lu...@googlegroups.com> wrote:

I've thought about current Lua's approach. Requiring strict ordering
(with inherited irreflection) makes some sense if we want to minimize
number of calls of comparison function.

But for me it's schizophrenic: trying to fit tertiary value into binary.
For me linear order comparison has three values: less, equal, greater.
You can't fit them into boolean and build sorting algorithm on that
without discovered side effects.

When you implemented sorting stuff, you learn the hard way using binary less-than is better.

If someone wants to use boolean comparators - he still needs two of them.
For example is_less() and is_equal(). Of course I won't be happy
to provide two almost identical blocks of code for them.

No, you do not. a==b can be done by ~((a<b) or (b<a))

But unless you are doing weird stuff you do not normally need it, as when you do a sorter you do not target a[i]<=a[i+1], you just target not(a[i+1]<a[i]). Testing too much makes a lot algorithms slower. 

i.e., when you do quicksort you choose a pivot, but you do not split the array in <pivot, ==pivot and >pivot, you just split in <pivot, pivot, not(<pivot). Sure, in arrays with zillions of dupes "fattening" the pivot may be a win, but normally it is a looser.

In bubble sort ( unused but known sweep-swap sorter ) you do not test three way, you just swap neighbours if out of order ( IIRC this also makes it stable, which may make it a good candidate for microsorts ). Similar things can be done with insertion or selection sort, which you should always use in place of bubble, that is for dydactic purposes only. And merge sort can also be done with one less-than usage per loop.

And in similar problems, like bsearch, you do similar things. A naive algorithm for bsearch may do start with l=1, h=#t, m=(l+h)//2, if m==x then return m, if m<x then l=m+1, else h=m-1, rinse and repeat.

But faster algorithms normally find the insertion point. They start with l=0, h=#t+1 ( so you know the possible position is after l before h ), get m, and then do if(m<x) then l=m else h=m, faster in the loop, and then, when l-h<2 you know the insertion point, if present, is at m. Then, if you wanted to find it you check if the insertion point is in the array and if the element there is equal. 

Sorting and searching algorithms are full of this kind of things.

For me requirement of comparison function to return one of three values
is more natural and acceptable than providing fragile sorting algorithm
for binary comparator.

It is initially easier to grok, been there. Once you implement some dozens you normally find boolean comparators lead to shorter, simpler and more robust code ( well, once debugged all sorting algorithms are robust ).

 

You can't even easily invert sorting like:

-- Ascending sort
table.sort(Orders, function(a, b) return DateIsLess(a, b) end)

-- Descending sort? Nah! Wandering runtime error!
table.sort(Orders, function(a, b) return not DateIsLess(a, b) end)

You can not do it that way, but you are falling in a trap:

table.sort(Orders, function(a, b) return DateIsLess(b,a) end)

is shorter and works. Lua reference is terse, but this example is found in lots of places.

Francisco Olarte.

[Francisco Olarte]

On Fri, 24 Apr 2026 at 18:16, 'Martin Eden' via lua-l <lu...@googlegroups.com> wrote:

That's right. Came to that after 40 seconds since I sent email.

I did not see this before I wrote the first one. 

But we can't say it's obvious, right? Besides, in real life there will
be several lines of code instead of "a, b".

It really is obvious. You do the same thing with three valued comparators for generality. cmp(b,a) works if cmp returns -/0/+ or true-nil-false or 2,"",-3.14. Not cmp will not work in many cases ( the usual is -/0/+ for C/asm convenience and tradition , and when you sort a lot you have "-cmp(a,b)" chiseled in a corner of your brain, but this mixes numeric and comparisons in an ackward way. 

 

Time spent in comparator is not limited. So sorting time may consist
mostly of time in that function. Imagine we're doing web request for
each comparison.. Imagine two times longer line of people in every
shop you visit..

This is why algorithms are coded to not test three ways. You do your web request but do not swap on not out of order. If you test a<b and get true, you put a before b, if false, b before a. No harm done if they are equal ( this is in a swapping/partitioning sort , if you are doing, say, an stable merge sort, you can do similar reasoning, but is too long to write )

 > I think having comparators be boolean "less than" functions makes some

> sense though.
> I want to be able to just write something like table.sort(t,
> function(a, b) return a > b end).
>
> Introducing a kind of "spaceship operator" seems like too much for a
> simple scripting language like Lua.
> What would the type of the result be? You could make it a number, of
> course, but that's really a hack.

Everybody ( well, C/C++, perl and others ) settles normally for -/0/+, as I said, it has tradition.

...

Boolean "less than" is perfectly fine. Problem that comparisons are costly.
So we spent like 24800 microseconds just to get data. And then
compare numbers and return 0 or 1. Which takes like 20 micros.

Ideally comparator should provide as much information about relation of
given items as it can. At least three output values if there is linear
order.
What sorting algorithm will do with them is his own business.

Boolean less than is fine, but if comparison is costly 3-way returns makes them costlier, and handling three-values results also makes control loops costlier.

Read the source of some good quick / insertion / heap / merge sort implementations are you will probably find why binary comparators are preferred in a lot of places.

Francisco Olarte.

[Martin Eden]

Thanks for replies, Francisco!

(bsearch is lame! cool kids code interpolation search with O(1) asymptotic!)

Let's talk about sorts!

Tony Hoare invented and published what is known as QuickSort in 1960.
(My university's mentor independently invented it in similar years
but was too late about publishing. He was sad about this all his life. :( )

You have array segment of items. You select some "pivot" item from segment
and split segment into several segments according to items relation to
that pivot item. Then you do recursive calls for them if it's needed.

Tricky part is produce that sub-segments inside original array segment
using constant memory. It's known as "partitioning".

Hoare's partitioning was two-way: "<" and ">=" (not "<").

Edsger Dijkstra published three-way partitioning in 1976.
There are "<", "==" and ">" parts. Profit here is that you exclude
sub-segments with equal values. They are never touched after initial
comparison with pivot and relocation.

Two-way partitioning requires just two-way comparator.
That's practically easy.

Three-way unsurprisingly requires three-way comparator.
That's mathematically nice.

But none of them uses "is_equal == not is_less(a, b) and not is_less(b, a)"
because it's two calls and is not needed.

(My note that you need two boolean comparators is wrong. Sorry about that.)


I'm stressing out that calling comparison function is a lot more
costly than executing algorithm. We are no longer sorting integers.

Execution time of comparator eclipse any cool algorithm coding in C.
We should try to minimize number of comparison calls.

And so three-way partitioning inherently requires less calls
of comparison function when there are some "equal" items.
But it requires three-way comparator (aka "spaceship operator").


I've implemented like 6-8 different sorts as programming assignments
in university. (But never needed them in career.) You have different
background. Have you ever met the case when you need to code effective
sorting in practice?

-- Martin

[Roberto Ierusalimschy]

>
> [...] Have you ever met the case when you need to code effective
> sorting in practice?

I really don't think this information is relevant to this list. Let us
avoid allowing arguments to get too personal. Thanks.

-- Roberto

[Martin Eden]

I agree here. Let's consider it as rhetorical question.

But I still want to discuss three-way vs two-way partitioning.
Current Lua uses two-way as a given fact. I want to evaluate
alternatives.

-- Martin

[sur-behoffski]

(Interesting discussion elided for briefness.)

Does the floating-point number NaN (assume IEEE754 etc.) always
compare as false to any other value, even another NaN?

If so, this could confuse some partitioning algorithms.

b

[Sean Conner]

It was thus said that the Great sur-behoffski once stated:

> (Interesting discussion elided for briefness.)
>
> Does the floating-point number NaN (assume IEEE754 etc.) always
> compare as false to any other value, even another NaN?

Yes. IEEE-754 requires that NaN is not equal to NaN. You can see this
yourself with Lua:

Lua 5.4.6 Copyright (C) 1994-2023 Lua.org, PUC-Rio
> x=0/0
> print(x,x==x)
nan false

-spc

[Francisco Olarte]

I, personally, did not take it personally, but as genuine curiosity. So I have decided it is better to trash my half written answer to the original and abort discussion. Anyone wanting to follow up, feel free to mail me privately.

Replying to this just for convenience.

Over & Out.

   Francisco Olarte.

[Lars Müller]

If passing NaNs may cause a sorting algorithm to produce an error, that's a feature. You must not try to sort the unsortable (and if you do, you should be explicit about how you want it sorted). -Lars

[Francisco Olarte]

On Sun, 26 Apr 2026 at 00:49, 'Lars Müller' via lua-l <lu...@googlegroups.com> wrote:

If passing NaNs may cause a sorting algorithm to produce an error, that's a feature. You must not try to sort the unsortable (and if you do, you should be explicit about how you want it sorted). -Lars

<kidding for="political correctness">

If you can sort by being explicit then it is nor unsortable, just "hard to sort".

</kidding>

The sorter goes through a comparator, it is easy to define one which sorts nan in a defined place, like some SQL engines do with nulls and NULLS FIRST/LAST clauses:

-- Sort NANs first, even before -Inf.

function nan_first_less(a,b)

   if is_nan(b) then

      return false -- NaN is not less than nothing, even other NaN

   elseif is_nan(a) then

      return true -- B is not a Nan, so a is less then it.

   else

      return a<b -- no NaNs, so this works right.

   end

end

is_nan is trivial and has been done here before. This can be used to sort NAN first or last. It can be optimized a bit by unrolling is_nan. Also, knowing floating point numbers are enumerable, you can place NaN anywhere in the FP range, but it is a bit harder, I do not recall if Lua sports signeds zeros, but with a proper comparator you can also do things like -0,NaN,+0, or signaling before non signaling nans.

IEE754 numbers are just a data chunk for a sorter, 64 bits in RAM, with a proper comparator they can always be sorted in any way you want, you just have to be a little careful writing it, as soon as you enter Nan (there are many representations for them, although I think lua just generates one)/Inf/unnormalized/signed zero territory things get a bit bug prone.

Francisco Olarte.

[Philippe Verdy]

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!

As a conséquence you always need to rewrite it.

--
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 lua-l+un...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/lua-l/9f0e3d7f-574f-4825-bb0c-642823cf60d0%40disroot.org.

[Lars Müller]

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

To view this discussion visit https://groups.google.com/d/msgid/lua-l/CAGa7JC0DZUOMFTr1a0WVa24itOtws9zTgtRGq-0ULe%2BqMYtRrw%40mail.gmail.com.

[Martin Eden]

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
> <ver...@gmail.com> 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

[Lars Müller]

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

--

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 lua-l+un...@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/lua-l/90534326-894a-4993-97b4-b6d4ad80e291%40disroot.org.

[Philippe Verdy]

Yes, by definition NaN is always different from everything (including NaN itself, unless you use an exact identity test, e.g. with ===, instead of normal equality test such as when 0 == 0.0 with different int/float/double types).

--
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 lua-l+un...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/lua-l/3b8f83f3-8a7a-44f9-8934-ef416f505988%40grouse.com.au.