Is it faster to merge and then sort, or sort and then merge?

Question

I have 2 arrays which are not sorted. Would it be faster to sort them individually and then merge them? Or would it be faster to just concatenate the arrays first and sort the combined huge array?

Answer 1

Assuming that concatenation is done in O(1), merging takes O(n) and sorting O(n log n), you have the choice between:

• sort and merge: O(n log n) + O(n) = O(n log n)
• concatenate and sort: O(1) + O((2n) log (2n)) = O(n log n)

therefore, asymptotically both options are equivalent.

Of course, the whole discussion is moot anyway if you use MergeSort.