Merge two arrays efficiently - one sorted, another unsorted

Question

I am working on a problem that has a sorted array of n elements followed by an unsorted array of length

1. O(logn)
2. O(sqrt(n))

How to sort the entire list most efficiently? Which sorting should I use in the above two cases?

Answer 1

Since inserting a single element into array and keeping it sorted is O(n), you cannot get better then that.

Thus, for both cases - sorting the smaller array and then using merge(part1,part2) will be O(n), and thus optimal in terms of asymptotic complexity.

• sorting the smaller array: O(logn*loglog(n)), or O(sqrt(n)*log(sqrt(n)) respectively of the cases.
• merge(part1,part2): O(n+logn) or O(n+sqrt(n)), which is O(n)¹ anyway.

So, the total complexity of both cases is O(n), which is optimal for this problem.

---

(1) It is true because, log(n)^k is asymptotically smaller then n^m for each k>0,m>0, and specifically for k=1, m=1/2.
Proof is based on taking logs on both sides:

log (log(n)^k) <? log(n^m) <=>
k*log(log(n)) <? m*log(n)

The last is obviously true (for large n and constant k,m>0), and thus the claim is true.
From this we can conclude that sqrt(n)*log(n) < sqrt(n) * n^1/2 = n, and thus it is indeed O(n).

Answer 2

You could simply sort the unsorted array and then do a merge (as in the merge sort algorithm) on those 2 sorted arrays.