Question

merge sort

Determine the best, average, and worst case inputs for merge sort.

Answer 1

Answer:

Time complexity of Merge Sort is O(n*Log n) in all the 3 cases (worst, average and best) as merge sort always divides the array in two halves and takes linear time to merge two halves.

Explanation:

We recursively divide the input array of size n into two parts of sizes n/2.This is the divide step which just calculates the indices of the two sub-arrays A[0..n/2] and A[n/2…n].So this step takes constant time i.e Θ(1).

Now,in the conquer step,we have to sort the two sub arrays and merge them. So,the complexity for this step is accounted in solving further smaller sub-problems of sizes n/4,n/8… and ultimately 1.

In the combine step,we are combining the elements of the smaller sub-arrays. Adding all of them,the number of elements is n. So we have to merge n elements in sorted order which will take Θ(n) time.

Since the divide step takes constant time,we can consider both collectively as Θ(n).

So the recurrence relation for time taken by merge sort will be:

T(n) = 2T(n/2) + Θ(n)

There is a 2 T(n/2) term since we have 2 sub problems each of size n/2 and Θ(n) time is required for divide and combine steps.

We can solve the above recurrence relation using the second case of the master theorem which leads us to the complexity Θ(nlogn).

Please give thumbsup, if you like it. Thanks.