Madeeasy testseries

Question

For merging two unsorted list of size m and n into sorted list of size m+n. The time complexity in terms of number of comparison for this is

Answer 1

In C language, we can use terms list and array interchangeably.

Approach 1 :

1. Sort both the lists individually using merge sort, so it will take Time complexity =O (mlogm+nlogn)

2. Then we get two sorted lists now we can apply merge algorithm (also known as combine algorithm in merge sort) and it will take time complexity of O(m+n) in worst case and min(m, n) in best case.

3. Also, we have to take one extra array of size m+n to store all m+n elements in one array.

4. Then we will get one sorted list of size m+n

so final T.C= mlogm+nlogn+(m+n)

             T.C=O(mlogm+nlogn)

 

Approach 2 :

1. Take one extra array and copy all m+n elements in it, which will take time complexity = O(m+n)

2. now apply merge sort, which will take Time complexity of (m+n)log(m+n)

3. Then we will get one sorted list of size m+n

so final T.C= (m+n)+(m+n)log(m+n)

              T.C=O((m+n)log(m+n))

also, if the size of both lists is n/2 then

T.C= ($\frac{n}{2}$+$\frac{n}{2}$)+($\frac{n}{2}$+$\frac{n}{2}$)log($\frac{n}{2}$+$\frac{n}{2}$)

which will be asymptotically represented as

T.C=O(nlogn).