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:
- Divide the full array into subarrays of size M.
- Run Selection Sort on each of the subarrays.
- 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.
2
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
2