Re: table.sort: invalid order function for sorting

On Fri, 24 Apr 2026 at 16:52, 'Martin Eden' via lua-l <
[email protected]> 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.

-- 
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%2BbJJbwyfD5Q2xGeNsz%2BcYrX2mWpU361kU0U5CvxBEy8PXnySA%40mail.gmail.com.