If I understand the code correctly (not guarenteed) then the minimum size after which a pre-shuffle is performed before quicksorting is 255.
/* QSORT_PLAY_SAFE is the size of the largest partition we're willing
to go quadratic on. We innoculate larger partitions against
quadratic behavior by shuffling them before sorting. This is not
an absolute guarantee of non-quadratic behavior, but it would take
staggeringly bad luck to pick extreme elements as the pivot
from randomized data.
*/
#ifndef QSORT_PLAY_SAFE
#define QSORT_PLAY_SAFE 255
#endif
Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail
"Memory, processor, disk in that order on the hardware side. Algorithm, algoritm, algorithm on the code side." - tachyon
|