Re: Soundness of table.sort

[Nagaev Boris <bnagaev@...>]

On Wed, Nov 4, 2015 at 10:49 AM, Dirk Laurie <dirk.laurie@gmail.com> wrote:
> 2015-11-04 8:17 GMT+02:00 takuya hashimoto <takuya.hashimoto@gmail.com>:
>>   function comp(l, r) return l <= r end
>>   list = {1,3,2,4}
>>   table.sort(list, comp)
>>
>> `comp` is an invalid order function for sorting,
>> but no error occurs, and `list` become {1,2,4,3}.
>> I think this is not a sound algorithm.
>
> The manual at present does not spell out what properties "comp"
> should have to be a valid function. Maybe it should say "At most
> one of `comp(a,b)` and `comp(b,a)` may be true."
>
> The Lua routine has some other undesirable properties apart
> from the one you mention.
>
> 1. It is not stable.
> 2. It has worst-case time of O(n²), and a sample worst case is
> explicitly known, so that a Lua-based server that at some stage
> sorts user-supplied input can be slowed down by a malicious user.
>
> It is based on a routine by Robert Sedgewick published in 1993,
> making it one of the oldest pieces of code in Lua. A lot has happened
> in the sorting world since then, and at least one [1] stable, in-place
> comparison sort with worst-case time of O(n*log(n)) is now known,
> which is however very complicated to program.

Thank you for sharing this algorithm!

Its implementation in C is about 1000 lines.
https://github.com/BonzaiThePenguin/WikiSort/blob/master/WikiSort.c

$ wc -l ltablib.c
357 ltablib.c

> On the other hand, a lot has also happened in the hardware world,
> and it is no longer very unreasonable to assume that there is enough
> memory for a clone of the table being sorted. In that case stability and
> worst-case efficiency can be achieved by a simple algorithm [2].
>
> Whether Lua itself should replace the very compact Quicksort code
> with something better but longer is a delicate decision of the kind
> that only the Lua team can make. Most of routines discussed in [2]
> are in pure Lua but do not carry a heavy performance penalty for
> not being in C.
>
> [1] https://en.wikipedia.org/wiki/Block_sort
> [2] http://lua-users.org/lists/lua-l/2013-05/msg00038.html and
>    follow-ups
>



-- 


Best regards,
Boris Nagaev