Re:A Killer Adversary for Quicksort (1999) [pdf]
by nightcracker on Friday October 30, 2015 @07:26AM
(#10477192)
I used this technique to prove libc++'s implementation of std::sort is O(n^2). There's still an open bug report for this in libc++: https://llvm.org/bugs/show_bug.cgi?id=20837.
On a related note, I'm talking to the libc++ and libstdc++ developers about replacing introsort with pdqsort (https://github.com/orlp/pdqsort) as the implementation for std::sort. It solves the worst case in a subtly different (and potentially more efficient) way than introsort. Although that's not the real selling point.
EDIT: I forgot I still use my old username on hacker news. To prevent confusion, I'm also the author of pdqsort.
On a related note, I'm talking to the libc++ and libstdc++ developers about replacing introsort with pdqsort (https://github.com/orlp/pdqsort) as the implementation for std::sort. It solves the worst case in a subtly different (and potentially more efficient) way than introsort. Although that's not the real selling point.
EDIT: I forgot I still use my old username on hacker news. To prevent confusion, I'm also the author of pdqsort.