Re: lhs and rhs in table.sort

[Coda Highland <chighland@...>]

On Thu, Aug 27, 2015 at 12:49 PM, Dirk Laurie <dirk.laurie@gmail.com> wrote:
> 2015-08-27 17:55 GMT+02:00 Coda Highland <chighland@gmail.com>:
>
>> I'm not sure about heap sort.
>
> Heap sort has best case, average case, worst case, all O(n log n),
> only the multipliers differ. Auxiliary storage O(1). See Nijenhuis and
> Wilf's book, available online [1].
>
> [1] http://www.math.upenn.edu/%7Ewilf/website/CombAlgDownld.html
>

Yes, I know this, but this analysis is based upon having a total
ordering. I'm pretty sure if I tried I could come up with an O(n log
n) worst-case algorithm that would nonetheless fail when given a
misbehaving predicate. Ultimately, this is a security question ("is it
possible to mount a DoS attack against this algorithm given control
over the comparator?"), not an algorithm analysis question.

That said, I did take some more time looking at a heap sort
implementation earlier and I think that a bogus predicate might be
able to trigger some bad performance (depending on the implementation
details) but not break it entirely since there's a fixed O(n)
insertions, and the sifting phase for each insertion is pretty trivial
to prove terminates.

/s/ Adam