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_b

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 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 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.