Re: Soundness of table.sort

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

2015-11-05 22:29 GMT+02:00 Roberto Ierusalimschy <roberto@inf.puc-rio.br>:
>> Indeed, but that isn't the attack model I had in mind. The interesting
>> take-away from this comparison function is that it gives you back a
>> table of integers, and if your sorting algorithm is deterministic and
>> does pivot selection in O(1) time, then said table exhibits bad
>> behaviour when sorted using the default comparator. Whereas
>> worstcase.lua synthetically constructs a worst-case input for the
>> particular pivot selection algorithm currently employed by table.sort,
>> adversary.lua organically constructs a bad-case input with no a-priori
>> knowledge of the pivot selection algorithm. Given the two totally
>> different methods of construction, I find it very pleasing that the
>> constructed arrays come out almost identical.
>
> My take-away was different: there is a high chance of very similar
> arrats, because there are only a few of them :-)  (Maybe the static
> one was built with a method similar to what 'adversary' uses?)

Yes.

When Albert Nijenhuis and Herbert Wilf wrote their seminal work
"Combinatorial Algorithms" back in 1975, they chose Heapsort
as the preferred sorting method because it is in-place, has O(n*log(n))
worst-case time, and among all algorithms with these two properties
known at the time was shortest to code (23 lines of Fortran) . I think
it still holds that particular record.