Total number of function calls in Merge sort Algorithm

Question

In Merge sort Algorithm when I took input array of size 2 and I got 4 function calls as including original function call with which I call MS algorithm i.e. MS (1,2) and which in turn calls two recursive function calls to merge sort as MS (1,1) and MS (2,2) and one function call to merge procedure as Merge (1,1,2)


Likewise for input array of size 3 I got 7 function calls.

for input array of size 6 I got 16 function calls.
So, how can I analyze the total number of function calls when input array size is n?


thank you!

Answer 1

For Merge Sort

no of times Merge Sort called = $2n - 1$

no of times merge is called = $n-1$

Comments

for input array of size 6 I got 16 function calls.

Answer 2

For ‘Merge-sort’ the number of function calls can be represented by T(n)

$T(n)=2T(\frac{n}{2})+2$, and T(2)=2

Solving which we get 2n-2, we add 1 for call from the main function, therefore (2n-1).

SImilarly for ‘Merge’ function

$T(n)=2T(\frac{n}{2})+1$ and T(2)=1

Which comes out to be (n-1).

Answer 3

for n=2    4 calls

for n=3    7 calls

for n=6     16 calls

thus for “n” calls “3n-2” calls

Answer 4

Total number of MERGESORT() calls = 2n-1

Total number of RECURSIVE MERGESORT() calls = 2n-2 (The very first call will not be a recursive call)

Total number of MERGE() calls = n-1