Intersection And Union Of Arrays

INPUT : Two Arrays "A" and "B" consisting of "n" and "m" elements respectively.

OUTPUT :
The union "U" of the two arrays and the intersection "I" of the arrays.
Example : if A = {1, 2, 4, 8}, B = {2, 6, 8, 10} then,
                U = {1, 2, 4, 6, 8, 10}, I = {2, 8}
Note : Since arrays are fundamentally different from Sets in the sense that every element is unique, we neglect the repeating elements in the union and the intersection as well i.e. if A = {1, 1, 1} and B = {1, 1} then, U = {1, 1, 1, 1, 1} and I = {1, 1}. This is because each element in an array is fundamentally unique.

OUR APPROACH :
 The first step is to sort each array in the same order (we used quick-sort to sort the array in ascending order). For each of the 2 functions (union and intersection), we maintain 2 pointers, one for each array. Now, we compare the elements at the ith position of A and jth position of B. Since the arrays are in increasing order, we know that if A[ i ] < B[ j ], the value equal to B[j] will be found only on the right side of i and vice versa. Thus, we traverse the 2 arrays and store the required elements.

The Java code for the said functions is as follows:
The Java implementation of QuickSort can be found here .
Note that, if we ignore the running time of QuickSort, the running time of each of the two functions is O(n+m).