Question

Q3. Answer the following questions: a) Explain why Merge sort is the most suited for very large inputs (that do not fit inside memory) while quick sort and heap sort are not as suited. Note that these three sorting techniques have comparable time complexities. b) Can Merge sort be performed in place? Explain your understanding.

no handwriting please

Answer 1

a) Merge sort is most suited for large inputs that do not fit in memory while quick sort and heap sort are not suited.

The reason is to perfrom quick sort or heap sort we need to consider all elements at a time.

merge sort is suitable because we can perform sorting using sub arrays,and sorted array can be copied back to secondary memory,and we can fetch the rest of the elements in various phases.

similary we can perfrom merging process for large set of data items.

in case of quick sort or heap sort we have to use all elements at a time, but they cant be copied to main memory at a time due to memory size costraint.

b)Can Merge sort be performed in place?

Merge sort cannot be performed in place, because while performing merging process, we merge two subarrays every time, we need to maintain temporary array to merge sub arrays in everystep until we reach the size of the original array.