Union, intersect, difference large IntSet in O(m+n) times

Question

from my question

http://stackoverflow.com/questions/3601472/insert-element-to-arraylist-with-ascending-order-and-no-duplicate-elements

i've done my insert method.

Now i try to find out union, intersect, and difference method to operate 2 IntSet.

Notice that number elements of IntSet is large and i need to do it in O(m+n) time where m and n is number of element of two IntSet

for example of Intset

a = new IntSetExtra();
b = new IntSetExtra();

for(int i=0; i<300; i++){ a.insert(2*i); }
for(int i=0; i<300; i++){ a.insert(i); }

for(int i=20000; i<50000; i++){ b.insert(i); }

how can i do it?

ps. it can use mergesort?

Thank you for your helping.

edit:

here is my union code

public IntSetExtra union(IntSetExtra a){
        //effect: return new IntSet that union between this and a;
        IntSetExtra intSet = new IntSetExtra();
        intSet.addAll(a);
        for(int i=0; i<a.size(); i++){
            if(!intSet.contains(a.get(i))){
                intSet.insert(a.get(i));
            }
        }
        return intSet;
    }

Answer 1

You may just use the methods of java collections such as addAll(Collection), removeAll(Collection) and retainAll(Collection).

For example, the intersection of two sets:

public Set<V> intersection(Set<? extends V> a, Set<? extends V> b) {
  // you may swap a and b, so a would contain the smaller collection
  Set<V> result = new HashSet<V>(a);
  result.retainAll(b);
  return result;
}