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

Question

I have 2 arrays that are not sorted. Would it be faster to sort them individually and then combine them? Or would it be faster just to compose the arrays and sort the combined array?

Answer 1

Clearly, big-O doesn't really say anything about this issue. Assuming the algorithm you are using is a quick sort. It has an average run time:

So, if sorting, then merging, we get:

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

merge and then sort:

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

The difference is

f2 - f1 = -n + 2.78n> 0

In general, if the sorting algorithm has complexity

C = k * nlog (n)

since k should usually be greater than 1 and it is unlikely to be somewhere around 0.5, sorting, then the merger will be faster if you assume that the cost of the merger does not exceed 2n.

Answer 2

Assuming concatenation is done in O(1) , the union takes O(n) and sorts O(n log n) , you have a choice between:

• sorting and combining: O(n log n) + O(n) = O(n log n)
• combine and sort: O(1) + O((2n) log (2n)) = O(n log n)

therefore, both options are asymptotically equivalent.

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

Answer 3

I think this will depend on the sorting algorithm and the size of your data.

But the wild hunch is that merging and then sorting the entire batch is preferable. Since the merge in this case is simply added.

While in another case you need to apply sorting.

Answer 4

When it is guaranteed that all records in the second array are larger than all in the 1st array, you can combine the arrays after sorting each one. Each sorting algorithm has a complexity that is worse than linear, so when you can break down the sorting task into subsets that can be sorted individually, you must do this.

But when records need to be sorted again after merging the arrays, sorting each array in advance is unlikely to make it faster.

If you want to know this for sure, create a large set of test data and evaluate the performance yourself.

Answer 5

It depends on the technique you use.

Sorting first and then combining will give the best results in modern multiprocessor architecture, where you can run sorting algorithms on both arrays in parallel threads around O(nlogn) (but with a much lower constant), and then combine them in O(n) time.