A recent (and interesting) discussion about quicksort.
Pattern-defeating Quicksort - Orson Peters
Conversation
Replying to
This is an oldie but a goodie describing adversarial quicksort oracle (uses popular B&M quicksort implementation, which the implementation from Postgres is derived from): cs.dartmouth.edu/~doug/mdmspe.p