The first list is sorted and the other is now unsorted, which is the best approach to merging both lists

Question

I have one sorted ArrayList A and one unsorted ArrayList B, now I want to combine the elements of B into A so that A remains sorted.

Now I can think of only two ways to do this.

The first is to sort Arraylist B, and then have two index positions, one for Arraylist A and the other for Araylist B, then we will move the index one by one to insert the list item B into A.

Assume that Arraylist A be the size nand size B Arraylist m.

The complexity order will be O(m Log(m))(to sort ArrayList B) + O(n + m).

The second approach has only an index in ArrayListaylist B, and then use Binary searchto place an element from Arraylist B to A.

The order of complexity will be O(Log(n) * m).

Now someone can tell me which approach I should choose, also if you can think of any other approach better than these two, please indicate.

Answer 1

It depends on the relative size nand m.

n > m*log(m) O(m*Log(m) + max(n,m)) n ( max(n,m)=n n > m*log(m)). O(log(n) * m) .

, , n m . , m n, .

:

, , , . , , ? , . , . , , , .

, , , O(m log(n)), .

Answer 2

1- : m * log (n) = O (mlgn)

: m * log (m) + n + m = O (mlgm)

if n <= m {
   1st approach
} else {
   2nd approach
}