Answer the following questions for the Merge Sort Algorithm i. How is the divisi

ID: 3683749 • Letter: A

Question

Answer the following questions for the Merge Sort Algorithm

i. How is the division of an array/subarray done by the algorithm during the partition step?

ii. How many recursive steps are required by this algorithm to reach the base case (= an

array with one element)?

iii. Use the Big-O notation to estimate the number of comparisons done by this algorithm at

each level of the recursive tree.

iv. Is merge sort algorithm in-place?

v. What are the recurrence relations for the best, average and worst cases of this algorithm?

vi. Use the Big-O notation to provide running times for the best, average and worst cases of

this algorithm.

vii. Provide an input and select the pivot point to get the worst case.

viii. Provide an input and select the pivot point to get the best case.

i. during partition step it divider the given list into two halves..upto the list is splited into single elements...

example:-

consider this list

5,6,3,2,8,4,5,6

5,6,3,2 8,4,5,6

5,6 3,2 8,4 5,6

5 6 3 2 8 4 5 6

ii)if list length is n then log n steps required...

because every time the list is divided into two halfs..

III)

at each level there are at max..O(n) comparisions..done by this algorithm...

iv)

No it not a inplace algorithm.. it uses additional space...

v)The recurrence relations for the best,average and worst cases all is same:-

vi.Running times:--

best:-O(nlogn)

average:-O(nlogn)

worst:-O(nlogn)

vii.viii.for best case and worst case pivot is same... it is middle element of the array.... it every time... make the array into two halfs...

example...

5,6,3,2,8,4,5,6

5,6,3,2 8,4,5,6

5,6 3,2 8,4 5,6

5 6 3 2 8 4 5 6

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