Disjoint set using Searching and Sorting

Question

I got a question in my algorithm class and i am unable to solve it. The question states that Theres is a Sorting Algorithm with O(nlogn) and searching is done by Binary search taking O(log n). Two sets are give P &Q and i have to design an algorithm to determine whether the two sets are Disjoint.

Answer 1

O(N) solution (assuming the two sets are sorted):

1. merge two sorted sets with information like the element belongs to which set
2. traverse through the merge list , if you find two equal elements from two sets than not disjoint else if are able to reach till end than disjoint

e.g.

a= 1, 4, 6
b= 2, 4, 7

Now merged set=

elements: 1 2 4 4 6 7

set no(a/b): 1 2 1 2 1 2

Now we can clearly see that two fours are consecutive and both are from two different set, hence not disjoint.

EDIT:

If your need is to find the sets are disjoint or not than simple merge will give you that. As soon as you find both elements in the sets are equal than just return saying not disjoint else if are able to reach till end of both than disjoint.

Question related to container. Below is that:

class Element{
int i;
int setInfo
}

Now declare array as: Element[] e=new Element[X];

Hope i am clear.

Answer 2

Two sets will be disjoint only if there is no common element between these two sets. I am assuming both of these sets have n elements each. This algorithm checks for common element in nlog(n) time. If there is no common element found that means both the sets are disjoint.

For each element in set "P" search whether that number exist in set "Q".
Time complexity - n*log(n) 
Log(n) to search in set Q and this search will be done "n" times.