Keep It Simple, Stupid PerlMonks

### Re: mergesort scratch space question

 on Oct 19, 2002 at 20:30 UTC ( #206562=note: print w/replies, xml ) Need Help??

in reply to mergesort scratch space question

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.

Replies are listed 'Best First'.
Re: Re: mergesort scratch space question
by demerphq (Chancellor) on Oct 20, 2002 at 19:40 UTC
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....

Create A New User
Node Status?
node history
Node Type: note [id://206562]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (3)
As of 2020-02-23 05:43 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
What numbers are you going to focus on primarily in 2020?

Results (102 votes). Check out past polls.

Notices?