Combine 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

• About (LOGN)
• O (SQRT (n))

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

Answer 1

Since inserting one element into an array and preserving its sorting is O(n) , you cannot improve it.

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

• sorting a smaller array: O(logn*loglog(n)) or O(sqrt(n)*log(sqrt(n)) respectively.
• merge(part1,part2) : O(n+logn) or O(n+sqrt(n)) , which is equal to O(n) ¹ .

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

---

(1) This is true because log(n)^k asymptotically less than n^m for each k>0,m>0 and, in particular, for k=1, m=1/2 .
The proof is based on the use of magazines on both sides:

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

The latter is obviously true (for large n and constants k,m>0 ), and, therefore, the statement is true. From this we can conclude that sqrt(n)*log(n) < sqrt(n) * n^1/2 = n , and therefore it is really O(n) .

Answer 2

You can just sort the unsorted array and then do merge (as in the merge sort algorithm on these 2 sorted arrays.

Answer 3

Simple, assemble the second part and combine it with the first (same as merging ). The step of merging two sorted subarrays is O (n).

Answer 4

Suppose part1 and part2 sizes r O (log n) and O (sqrt (n)), respectively. So, if you select one element from part2 and find the position in part1 in the log (log n) using binary search and do it recursively until the part2 elements are empty, the total runtime becomes O (sqrt (n) log (log n ) ).