G'day builat,

To determine whether some piece of code is faster than another, use the Benchmark module. (In case you didn't know, this is part of the standard Perl distribution: you'll already have it installed.)

Specifically for sorting routines, take a look at both the sort function and the sort pragma. Note the various caveats and warnings, particularly with respect to usage with different Perl versions and deprecation of '_SUBPRAGMA'.

I ran a few tests with the code you've presented here. Your sortQ() routine is roughly an order of magnitude slower than the standard "sort { $a <=> $b } ..." (ascending, numerical) code.

I also found that with (what I'd consider) small arrays of just a few hundred elements, and a relatively high number of duplicates, I got screenfuls of "Deep recursion on subroutine "main::sortQ" ..." messages.

So, test your code with various array sizes, numbers of duplicates (which equates to the range of random numbers) and any other variable factors. Only when you have code that passes your tests should you consider benchmarking: it doesn't matter how fast broken code completes!

-- Ken

In reply to Re: quick sort. How do it faster by kcott
in thread quick sort. How do it faster by builat

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.