| > It is, they're both qsort. Oh! No, that's not a thing. What's happened there is you saw that the libc function was named qsort and you went "I am smart, I know that means Tony Hoare's Quicksort algorithm from the 1960s" but that's not what it means, it is named that way but it's only defined as an unstable sort, the libc does not promise any particular algorithm. Over in C++ land they also don't specify the sort algorithm used but in C++ 11 they mandated that the provided function must have worst case O(n log n) performance. This is awkward for Quicksort because although Tony's algorithm is very fast on average, its worst case is O(n squared) which is very slow Thus, conforming C++ libraries are definitely not a Quicksort. Now, conformance to the C++ ISO standard is basically a minor curiosity and nobody cares, so Clang for example just didn't bother and shipped a Quicksort anyway until relatively recently, but already we can see that we're by no means guaranteed these are "both qsort" nor that they're both anything in particular. The thing you should do is an introspective sort or "Introsort". There are a lot of these, for some time the best general purpose algorithm was PDQsort, the Pattern Defeating Quicksort by Orson. But even though that word "Quicksort" is in there this is not just "Well it's qsort so it's the same anyway" any more than a Cayenne is the same as a road legal 911 is the same as Porsche's 963 track car. |