in reply to Bitten by the worst case (or why it pays to know whats inside the black box)

its not clear to me if this is still true in 5.8

Perl 5.8 defaults to mergesort on most platforms, though quicksort is still available through use sort '_quicksort';.

The mergesort algorithm does not have the nasty worst case performance which bit demerphq. It guarantees to run in O(NlogN) time. It is also stable, meaning that items which compare equal in the sort retain their order in the result. Its disadvantage is that it uses O(N) memory for temporary storage.

After Compline,
Zaxo

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

Replies are listed 'Best First'.
Re^2: Bitten by the worst case (or why it pays to know whats inside the black box)
by Fletch (Bishop) on Jun 27, 2004 at 00:38 UTC

    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 . . .).

[reply]
[d/l]

      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