Re: Soundness of table.sort

[Tim Hill <drtimhill@...>]

> On Nov 3, 2015, at 11:49 PM, 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.
> 
> 
> 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.
> 

I wonder what the profile of tables using the sort() function looks like (in terms of # of items being sorted etc)? If there is a clear boas toward smaller tables, then a dual algorithm that forks based on size of table might be a good idea (smaller tables get faster sort using a copy-based algorithm larger tables get in-place sort that is slower but doesnt take the memory hit).

Of course, this means more code and more code paths (and testing), which is not good, but is better imho than everyone rolling their own sort to bypass perceived issues with the built-in sort() function.

—Tim