lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

On Wed, Nov 4, 2015 at 10:49 AM, Dirk Laurie <> wrote:
> 2015-11-04 8:17 GMT+02:00 takuya hashimoto <>:
>>   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.

$ 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]
> [2] and
>    follow-ups


Best regards,
Boris Nagaev