Because it is more complicated than it has to be?

Observe. Let one of the slices to be aligned at the top of the pre-allocated space that the merge will go into. Then the merge can be safely done with no need for any FIFO, the slice in the allocated space is eaten away as the merged set grows beneath it.

With this knowledge we can implement a destructive copy_sort, that copies data from one buffer to another, sorting in the process. Implementation. If you have one element then move it. If you have more, then copy_sort the top half of the first buffer to the top half of the second. Then copy_sort the bottom half of the first buffer to the top half of the first buffer. Now merge first and second buffers in the second.

Now you can implement a merge_sort that works in place scratch size of about N/2 without loss of efficiency. Allocate the scratch area. Then copy_sort the top half of the original data to the scratch area. Now copy_sort the bottom half of the original data to the top half of the original space. Merge the two in the original space. Free the scratch region. Return.

If you are hard up on space, you can lose some efficiency but only need 1/3N scratch. Allocate scratch area. copy_sort the top third to the new space. copy_sort the bottom third to the top third. copy_sort the middle-third into the bottom third. Merge bottom third into the top third using the top 2/3. Merge scratch area back. Free the scratch region. Return.

Other variations on the theme are certainly possible.

I haven't heard of anyone implementing any of these, which mainly means that I never looked. Most presentations of common algorithms try to get the basic idea across, not the best implementation. And sorting is probably the most heavily studied algorithm problem, so you won't have a new (good) sorting idea at random.

In reply to Re: mergesort scratch space question by Anonymous Monk
in thread mergesort scratch space question by nothingmuch

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.