Question

Ryan is implementing a merge sort algorithm that he heard about in computers class. However, he was not paying attention, and ended up implementing the merge sort in a very unusual way. The standard merge sort takes a list, and recursively splits it in half, until there is only one element left. It then uses the idea that two sorted lists can be easily merged in O(n) time using "two pointer technique" (this step is usually called merge). Ryan does not know about two pointer technique, so he decided to replace merge with a bubble sort! The bubble sort runs in O(n^2) time. What is the runtime of this merge sort implementation?

Answer 1

Merge sort:

Merge sort is an sorting technique which uses divide and conquer method for sorting the set of elements recursively,hence less consuming less time.It run in 0(n*logn) time in all the cases.It divides the input array in to 2 halves ,call itself for the 2 halves and then merges the 2 sorted halves.

Run time analysis :

Merge sort algorithm

Public static void sort(double[ ]a,int left,int right, double [ ]tmp);

{

Double left, right;

If(left-right)==1)

{

Return;

}

Int middle=(left+right)/2;

Sort(a,left,middle,tmp);

Sort(a,middle,right,tmp);

Merge(a,left,middle,right,tmp);

}

Define:T[N]=statement that u need to execute to merge sort an array of N elements

From merge sort algorithm we can see that

Sort(array of N elements)

Will call:

Sort(array of N/2 elements);

Sort(array of N/2 elements);

Merge(array of N elements);

There fore:

Amount workdone by sort(array of size N)=

Amount workdone by sort(array of size N)+amount workdone by sort(array of size N)+N

Or

T(N)=T(N/2)+T(N/2)+N

Further more:

T(1)=1//time to execute if statement

*The performance of merge sort is given by recurrence equation=

T(N)=n*T(N/2)+N....(1)

T(1)=1......…................(2)

Solving the reccurence equation we get

*We use the expansion method to find a solution then we can detect a pattern

T(N)=2*T(N/2)+N

4*T(N/4)+2*N =2^2+T(N/(2^2))+2*N

For simplicity we can assume N= some power of 2

N=1024(2^10)

*N=2^k then we can solve can solve exactly as follows:

T(N)=(2^k)+T(N/2^k)+k*N like this

The final result will be

=(Log(N)+1)*lg(N)

Since sorting an array of size N=2^k will take

running time of merge sort =( log(N))+1*N

then sorting array size<2^k will take atmost

running time of merge sort <=(log(N))+1*N

There fore the running time of merge sort to sort an array of size N is bounded by :

(Log(N))+1*N=0(N*log(N))

​​​​​