Sorting

Question

Two unsorted arrays of size m and n are to be sorted into a single array, what is best case time complexity?

Comments

incomplete question

What is difference between sorting 1 array and sorting 2 arrays??

---

m+n log (m+n)

---

And why not like this
If we sort first array, mlogm
For second, nlogn
And after that we can take two sorted arrays and apply merge sort, that will take O(m+n)
So total, O(mlogm+nlogn+m+n) = klogk, k=max(m, n)
Isn't this approach right?

---

@shrma read your 4th line

---

Yes got it buddy, since mlogm and nlogn are of same order, so can't ignore one.

Correct?

Answer 1

First sort both arrays and then combined into a single array, complexity = m log(m) + n log(n) + (m+n)

First combine into a single array and then sort the combined array, complexity = (m+n) log (m+n)

Comments

Combine in a single array done by heapification?

---

@suraj in the first line it should be nlog(n)

---

Thanks. Corrected now.

Answer 2

Simply combine both arrays then resultant array will have m+n elements.

Then apply best sort method on O(nlogn) which will give here (m+n)log(m+n)

So here by combining and then sorting is efficient.

Answer 3

We can sort both arrays using Linear sort and Linear sort take O(n+k) time and after sorting them we can merge them into one array. For merging O(n) time taken so total time complexity will be:-

2.(O(N+k)) (sorting) + O(n)(for merging)  so it is some how equal to O(n).