Both QuickSort and MergeSort require splitting the input array into two smaller

Question

Both QuickSort and MergeSort require splitting the input array into two smaller arrays, recursively sorting the subarrays, and then joining the sorted subarrays to obtain a sorted version of the initial input array. One way to handle the recursive calls is to allocate new memory for the subarrays, copy the elements from the input array to the newly allocated memory, and pass these new subarrays in the recursive call. However, this requires a lot of extra memory.

1. In MergeSort, each sub-array is approximately half the size of the input array. Suppose the original input array originally used n units of mem- ory. Suppose we allocate new memory for the subarrays every time the array is split. Then over the entire set of recursive calls, how much total memory is required?

2. Describe how QuickSort can be implemented in place (that is, without allocating new memory for the subarrays). If you need a small amount of memory for temporary storage, that’s fine.

Explanation / Answer

1 .

(N/2)^1+ (N/2)^2+ (N/2)^3+...

=

2. If we select last element as pivot, we don't ahve to allocate new memory for subarrays. Just one temporary storage will be enough to get the min or max from reminder list and putting them to temp storage again for future. so in this case only small amount of memory to sort the list .

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.