Re: mergesort scratch space question

[Anonymous Monk]

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.

[demerphq]

so you won't have a new (good) sorting idea at random.

Indeed. And considering that merge sorting was one of earliest sorts to be studied and considered (von Neuman suggested it in 1945) a truely signifigant improvement based on its ideas is probably especially unlikely.

--- demerphq
my friends call me, usually because I'm late....