Hi Jasen! :-)

 PS>> Quicksort has a worst-case of O(n^2), in the case of an already
 PS>> sorted array. But your right, on random data it's O(n log n)
 JB> Most implementations of qsort() have code to handle that case better.
Hard to check for, I'd think. The glibc version has quite a lot of
optimizations, though. For example, it falls back to insertion sort (I
think it was that) under a certain partition size where qsort'ing the
remaining partition would be slower (machine-dependend threshold, even).

Ciao
Pascal

--- Msged/LNX 6.1.1