There's no test against the built-in sort to check that your sorts are correct.

True, but for this post, I reduced a much larger testing program to what was needed to make my case. If you look at my code, you will see commented out statements printing the result of the sort for each algorithm. I have tested many cases, and haven't seen any case with something incorrect. I do believe that my sort implementations are correct, possibly not optimal, but correct.

I would have been interested to see timing comparisons of the two different built-in sorts that are available, quick and merge, versus the random and pathological data sets you're using.

You are right again. I was thinking of doing it, but did not take the time. I might come up with that if I have the energy of doing it. It is almost midnight in my timezone now, I might give a try, but only if that does not take too long.

Are there any other pathological data sets to throw at these two sorts?

I do not know, the two cases I have shown are the most well-known cases and the only ones I have really tested (but, as I said in one of my posts above, they are much more common than one might think, because you quite often have to sort data that is already almost sorted). I *think* that an array where there are really many duplicates also show pathological behavior for quick sort, but I don't think I have checked.

In reply to Re^6: sort behavior explanation required by Laurent_R
in thread sort behavior explanation required by ghosh123

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.