In C language, we can use terms list and array interchangeably.
Approach 1 :
- Sort both the lists individually using merge sort, so it will take Time complexity =O (mlogm+nlogn)
- 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.
- Also, we have to take one extra array of size m+n to store all m+n elements in one array.
- 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 :
- Take one extra array and copy all m+n elements in it, which will take time complexity = O(m+n)
- now apply merge sort, which will take Time complexity of (m+n)log(m+n)
- 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).