Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I am reviewing basic algorithms from a book called Algorithms by Robert Sedgewick, and I came across a problem in MergeSort that I am, sad to say, having difficulty solving. The problem is below:

Sublinear Extra Space. Develop a merge implementation that reduces that extra space requirement to max(M, N/M), based on the following idea: Divide the array into N/M blocks of size M (for simplicity in this description, assume that N is a multiple of M). Then, (i) considering the blocks as items with their first key as the sort key, sort them using selection sort; and (ii) run through the array merging the first block with the second, then the second block with the third, and so forth.

The problem I have with the problem is that based on the idea Sedgewick recommends, the following set of arrays will not be sorted: {0, 10, 12}, {3, 9, 11}, {5, 8, 13}. The algorithm I use is the following:

  1. Divide the full array into subarrays of size M.
  2. Run Selection Sort on each of the subarrays.
  3. Merge each of the subarrays using the method Sedgwick recommends in (ii). (This is where I encounter the problem of where to store the results after the merge.)

This leads to wanting to increase the size of the auxiliary space needed to handle at least two subarrays at a time (for merging), but based on the specifications of the problem, that is not allowed.

I have also considered using the original array as space for one subarray and using the auxiliary space for the second subarray. However, I can't envision a solution that does not end up overwriting the entries of the first subarray.

Any ideas on other ways this can be done?

NOTE: If this is suppose to be on StackOverflow.com, please let me know how I can move it. I posted here because the question was academic.

share|improve this question
    
extra space requirement is max(M, N/M) so you can allocate a new size M block for the merg in step 3 –  ratchet freak Dec 14 '12 at 13:35
    
@ratchetfreak Are you saying this is in addition to the auxiliary space used in the traditional MergeSort implementation? –  hulkmeister Dec 14 '12 at 13:55

1 Answer 1

up vote 3 down vote accepted

to merg 2 blocks of size M you only need M extra space:

if you have a block from i to j and a block from j to k you first copy the first block to the additional space so i to j is free to recieve the sorted array

then the merge is implemented as:

extra = new array[j-i]
arraycopy(arr,i,extra,0,j-i)//copy from arr to extra
p =0
while i<k
    if(arr[j]<extra[p])
       arr[i++]=arr[j++]
    else
       arr[i++]=extra[p++]
    if(j==k)break;
    if(i==j)break;
end while
arraycopy(extra,p,arr,i,extra.length-p)//copy remaining from extra

you can see that i only increments without j up to j-i times so i is never larger than j

share|improve this answer
    
Thanks for the response. This makes sense and I can see that I went wrong with thinking the original entries would get overwritten if I also used the original array as storage for one of the subarrays. I have another question - this merge works, but from what I understand I am to repeat this from one pair of blocks to the next, how does this method sort the array as a whole? The counterexample I present in the question is a real hindrance in my head. –  hulkmeister Dec 14 '12 at 15:27
    
it doesn't sort the entire array unless you repeat it N/M times, making the entire algorithm of O(n^2) time complexity –  ratchet freak Dec 14 '12 at 15:56
    
That's what I thought. Thank you! –  hulkmeister Dec 14 '12 at 18:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.