Question

Describe a variation of the merge-sort algorithm that is given a single array, S, as input, and uses only an additional array, T, as workspace. No other memory should be used other than a constant number of variables.

Answer 1

Step 1 - If it is only one element in the array S it is already sorted, return.
Step 2 - divide the array recursively into two halves until it can no more be divided.
Step 3 - merge the smaller arrays into new array T in sorted order.And store merged sorted array in array S.

MergeSort(S[], l, r ,T[])
If r > l
1. Find the middle point to divide the array into two halves:  
middle m = (l+r)/2
2. Call mergeSort for first half:
Call mergeSort(S, l, m ,T)
3. Call mergeSort for second half:
Call mergeSort(S, m+1, r ,T)
4. Merge the two halves sorted in step 2 and 3 and store it in temporary array T:
Call merge(S, l, m, r , T)
5. Restore back the sorted merged array T into array S .