Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
PerlMonks  

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

by Zaxo (Archbishop)
on Jun 26, 2004 at 16:10 UTC ( [id://369839]=note: print w/replies, xml ) Need Help??


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

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

      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

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://369839]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others imbibing at the Monastery: (3)
As of 2024-03-28 18:09 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found