in reply to Re: 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)

Also note that perldoc sort also says after 5.8 that "large arrays" are shuffled before sorting if you tell perl to use quicksort (although it doesn't specify how large "large" is . . .).

  • Comment on Re^2: Bitten by the worst case (or why it pays to know whats inside the black box)
  • Download Code

Replies are listed 'Best First'.
Re^3: Bitten by the worst case (or why it pays to know whats inside the black box)
by BrowserUk (Patriarch) on Jun 27, 2004 at 01:04 UTC

    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
[reply]
[d/l]

In Section Meditations