Tim Peters <tim.pet...@gmail.com> added the comment: [Marc-Andre] > BTW: I wonder how long it's going to take before > someone figures out that our merge sort based > list.sort() is vulnerable as well... its worst- > case performance is O(n log n), making attacks > somewhat harder.
I wouldn't worry about that, because nobody could stir up anguish about it by writing a paper ;-) 1. O(n log n) is enormously more forgiving than O(n**2). 2. An attacker need not be clever at all: O(n log n) is not only sort()'s worst case, it's also its _expected_ case when fed randomly ordered data. 3. It's provable that no comparison-based sorting algorithm can have better worst-case asymptotic behavior when fed randomly ordered data. So if anyone whines about this, tell 'em to go do something useful instead :-) ---------- nosy: +tim_one _______________________________________ Python tracker <rep...@bugs.python.org> <http://bugs.python.org/issue13703> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com