Note that the mergesort implemented by Perl isn't the stock mergesort you see in the textbooks.

It's a special version of mergesort that takes advantage of runs of already sorted (or reversed sorted) items. While at the same time making sure the sort is stable. This makes sorting of (almost) sorted lists faster than stock mergesort would give you.

The quicksort implemented by Perl has some defenses against poor performance as well. Traditional quicksort is behaves quite poorly on sorted lists (with naive textbook implementation even going quadratic). Perls quicksort does some smart pivot picking (middle-of-three, IIRC) - but it can still behave badly on pipe-organ shaped lists. As an extra defense, if quicksort is picked, and the list is larger than a certain size, the list will be shuffled first.

In reply to Re^2: how sort works by JavaFan
in thread how sort works by Complex13

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.