# Sublinear Extra Space MergeSort

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.

• extra space requirement is max(M, N/M) so you can allocate a new size M block for the merg in step 3 Dec 14, 2012 at 13:35
• @ratchetfreak Are you saying this is in addition to the auxiliary space used in the traditional MergeSort implementation? Dec 14, 2012 at 13:55

To merge 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 receive 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`

• 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. Dec 14, 2012 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 Dec 14, 2012 at 15:56