Is Ms vc6 qsort known to be 'smart' about already sorted array?
I'm getting ready to do some sorting of a small'ish array. (300 to 1000 elements). In general, it will already be sorted, or almost sorted. My understanding is that some implementations of qsort become quadratic with an array that is already sorted. Does anyone know specifically if this applies to MicroSoft's implementation in visual c++ 6, sp5? Preferrably, this would include a link to something authoritative with, ideally, a test program.
I could write a quick 'proof-of-concept' program, but would rather ask this forum.
A related question ... my impression is that a variant of a quadratic sort algorithm turns out to be 'good enough' for almost sorted arrays. Is this the 'shell' sort? Can some 'smart' implementations of qsort detect an already (or almost) sorted list and use another algorithm for this partition? Or use a simple quadratic sort variant when the partition get small?