in reply to Re^2: Bitten by the worst case (or why it pays to know whats inside the black box)
in thread Bitten by the worst case (or why it pays to know whats inside the black box)

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

[download]
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
  • Comment on Re^3: Bitten by the worst case (or why it pays to know whats inside the black box)
  • Download Code

In Section Meditations