Find intersection of two arrays without duplicates

Strictly speaking, the presence of merge sort disqualifies the solution: standard merge sort has \$O(n)\$ space complexity (an in-place merge sort still requires \$O(\log n)\$ space). Use heap sort instead.

EDIT.

There is no much you can do to speed it up in terms of asymptotical behavior. You can shave off some cycles by not using binary search (which is horribly referentially unlocal). Instead, sort both arrays and merge-intersect them, along the lines of

sort(a);
sort(b);
for (i = 0, j = 0; i < size(a) && j < size(b); ) {
    if (a[i] < b[j])
        ++i;
    else if (a[i] > b[j])
        ++j;
    else {
        handle_intersection();
        ++i;
        ++j;
    }

But my solution doesn't utilize the property that "no duplicate elements in the array".

But it does. Try adding a duplicate 5 to b:

A = [9, 1, 4, 2, 5]
B = [3, 1, 8, 7, 6, 5, 5]
Intersection => [1, 5, 5] Wrong!

You get an incorrect result. To handle that correctly, you'd have to do more work.

The bigger problem is that your solution uses \$O(\min(n, k))\$ space, not \$O(1)\$. To be precise, it uses size of the intersection space, which is limited by the smaller of \$n\$ and \$k\$. To use \$O(1)\$ space, you'd have to return either a or b as the result, not allocate new memory.

private static List<Integer> getIntersectionO1Space(List<Integer> a, List<Integer> b)
{
    // from janos' 3rd paragraph
    if ( a.size() > b.size() ) {
        getIntersectionO1Space(b, a);
    }

    mergeSort(a); //Time O(k log k), space O(1)

    for ( Iterator<Integer> iterator = b.iterator(); iterator.hasNext(); ) //O(n log k)
    {
        int r = Collections.binarySearch(a, iterator.next()); //O(log k)
        if (r < 0) {
            iterator.remove();
        }
    }

    return b;
}

To handle duplicates, you'd add

        } else {
            a.remove(r);

My test function looks like

public static void main(String[] args) {
    List<Integer> a = new ArrayList<Integer>();
    a.add(9);
    a.add(1);
    a.add(5);
    List<Integer> b = new ArrayList<Integer>();
    b.add(1);
    b.add(3);
    b.add(5);

    System.out.println(getIntersectionO1Space(a, b));
}

I didn't do much more testing than that.