Re: Soundness of table.sort

[Roberto Ierusalimschy <roberto@...>]

> 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?)

-- Roberto