First list is sorted and the other is unsorted now which is the better approach to merge both list

user_4062630 0
Viewed 160

I have one Sorted ArrayList A and one unsorted ArrayList B, now I want to merge items of B in A such that A remains sorted.

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

First one is to sort Arraylist B and then have two index positions one for Arraylist A and other for Araylist B, then we will move index one by one to insert B list's item in A.

Let us assume size of Arraylist A be n and size of Arraylist B bem.

Order of complexity will be O(m Log(m))(for sorting ArrayList B) + O(n + m).

Second Approach is just have an index on ArrayListaylist B and then use Binary search to place item from Arraylist B to A.

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

Now can anybody please tell me which approach should i opt, also if you can think of any other approach better than these two then please mention.

arraylist time-complexity sorting android java
2 Answers

It depends on the relative size of n and m.

When n > m*log(m) the run time of the first algorithm with complexity O(m*Log(m) + max(n,m)) would be dominated by that linear term on n (notice in this scenario max(n,m)=n as n > m*log(m)). In this case the second algorithm with complexity O(log(n) * m) would be better.

The exact practical cutoff point would depend on the constant factor for each algorithm particular implementations, but in principle, the second algorithm becomes better as n gets bigger in relation to m, and eventually becomes the better option. In other words, for every possible value of m there exists a big enough value for n for which the second algorithm is better.

EDIT: THE ABOVE IS PARTLY WRONG

I answered assuming the given complexities for both algorithms, but now I'm not sure the complexity for second one is correct. You propose inserting each number from the unsorted list into the sorted list using binary search, but how exactly would you do this? If you have a linked list you can not do binary search. If you have an array you need to displace part of the array on each insert and that is a linear overhead on each insert. I'm not sure if there is a way to achieve this with a more complex data structure, but you can not do this with either a linked list or an array.

To clarify, if you had two algorithms with those time complexities, then my original answer holds, but your second algorithm doesn't have the O(m log(n)) complexity we assumed.

user_22263930

1st Approach: m * log(n) = O(mlgn)

2nd Approach: m * log(m) + n + m = O(mlgm)

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