A killer adversary for quicksort

Quicksort can be made to go quadratic by constructing input on‐the‐fly in response to the sequence of items compared. The technique is illustrated by a specific adversary for the standard C qsort function. The general method works against any implementation of quicksort – even a randomizing one – that satisfies certain very mild and realistic assumptions. Copyright © 1999 John Wiley & Sons, Ltd.