Worst case performance and "impossibly unlikely" conditions

Posted Jan 14, 2012 23:03 UTC (Sat) by vonbrand (subscriber, #4458)
In reply to: Worst case performance and "impossibly unlikely" conditions by rgmoore
Parent article: Denial of service via hash collisions

Here are a few references on quicksort's worst case in my reference list.

Muser, David, "Introspective Sorting and Selection Algorithms", Software -- Practice and Experience, 27(8), 983-993 (1997), in PostScript
McIllroy, M. Douglas, "A Killer Adversary for Quicksort", Software -- Practice and Experience, 29(4), 341-344 (1999)