Question

Let us suppose that there are n elements in the un-sorted array. Answer the following?

q1: How is merge sort different from quick sort?

q2: What is the split ratio in merge sort?

q3: What is the worst-case/average-case/best-case running time of Merge Sort?

q4: Why is the worst case running time of Merge sort O(n log n) always?

q5: Why does Merge Sort use a static tree in the recursion process? (It is worth noting that the Quick Sort use a dynamic tree.)

Can Somebody help answer these questions and ill give a thumbs up

Answer 1

Answer:

1 - Merge sort without any consideration first divides the current array in 2 equal halves, recursively sorts both the halves and then, using the technique of merging, merges both the half sorted arrays in linear time. Quick sort picks a pivot element, moves all the array elements such that this pivot element gets to its correct position in the sorted array, and the recursively sorts both the left and right parts (arrays) of the pivot element. Note that there is no technique of merging here because both the left and right parts will not overlap in the sorted arrays (as all the elements of right side are greater than all the elements on the left side).

2 - Merge sort divides the array into 2 equal halves so the split ratio is 1 : 2. There are other variants of merge sort where we divide the array into 3 equal parts (here split ratio will be 1 : 3).

3 - ​​​​​​Worst case = , average case = , Best case = . So basically merge sort always has a running time complexity of .

4 - Merge sort complexity in the worst case is always because it recursively divides the arrays into equal halves until the size of current array becomes 1. Number of times this has to be done is (this is from the property of logarithm) and in each of these steps merging of all the array parts is done which total means order of n comparisons and swapping. So overall complexity becomes . This is always the case because merge sort doesn't divides the arrays after looking at the elements, it first divides the array, calls the sort of each individual halves and merges them. Even if the array was initially sorted, it would not know and so it will divide the array and sort individual halves and merge them. Thus there is no change in running time of merge sort for any kind of input.

5 - Static tree here implies that in recursion of merge sort the partition are done in the same way always(in the middle of the array), which is quite clear from the previous arguments. In quick sort, whatever method we use to select the pivot element, for different inputs, the correct position of this pivot element in the array might be different. This means for different inputs the size of left and right parts will be different and so the recursion tree can be said to be dynamic in nature.