Re: table.sort: invalid order function for sorting

On 2026-04-24 16:21, Philippe Verdy wrote:
> 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()!

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

-- 
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/a832ad81-b9e5-47ac-af82-48c666412809%40disroot.org.