Re: Soundness of table.sort

[Dirk Laurie <dirk.laurie@...>]

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.

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