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?

Accepted Answer

Clearly, big-O isn't really saying anything in this problem. Assuming the algorithm you are using is quicksort. It has a average running time of:

So now, if sort then merge we get:

f1 = 1.39n * log(n) * 2 + 2n

merge then sort:

f2 = n + 1.39 * 2n * log(2n)

The difference is

f2 - f1 = -n + 2.78n > 0

In the general case, if a sorting algorithm has complexity

C = k * nlog(n)

then since k should be normally bigger than 1, and isn't likely to be anywhere near 0.5, sort then merge will be faster if you are assuming the merge costs at most 2n.

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

Solution

Problem