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 a workspace. No other memory should be used other than a constant number of variables. Compare the time complexity of the variation to the normal merge-sort algorithm.
ANSWER :
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 .
I tried my best... hope it helps... please give an upvote. it's very important to me.. thank you:)
Get Answers For Free
Most questions answered within 1 hours.