On: Algorithmic complexity attacks and libc qsort()

[CJefferson]

Just in case anyone is curious, this does not effect any implementation of std::sort in C++ I am aware of.

They all use introsort -- basically use quicksort until you have done some number of partitions, then switch to heapsorting the cells of the partition. This ensures fast quick-sort performance while guaranteeing O(n log n) worst case.

[comex → CJefferson]

In Linux-land, glibc's qsort also uses introsort, and musl libc's uses smoothsort:

http://www.etalabs.net/compare_libcs.html