Find intersection of two arrays without duplicates A = [9, 1, 4, 2, 5] k unique integers
  B = [3, 1, 8, 7, 6, 5] n unique integers
  Intersection => [1, 5]


Find an algorithm that uses \$O(1)\$ space (the space used by the return variable is not considered) and runs as fast as possible to find the intersection of the arrays.  

private static List&lt;Integer&gt; getIntersectionO1Space(List&lt;Integer&gt; a, List&lt;Integer&gt; b)
{

    List&lt;Integer&gt; intersection = new ArrayList&lt;Integer&gt;();
    mergeSort(a); //Time O(k log k), space O(1)

    for (Integer n : b) //O(n log k)
    {
        int r = Collections.binarySearch(a, n); //O(log k)
        if (r &gt; -1)
            intersection.add(n);
    }
    return intersection;
}


So the total time complexity is \$O(\max(k,n) \log k)\$.

But my solution doesn't utilize the property that "no duplicate elements in the array". I wonder whether there is an algorithm that uses the property and runs faster.
Your solution doesn't have explicit instructions to use the property that no duplicate elements in the array, but it naturally benefits from it.
The binary search is slightly faster because it doesn't need to visit duplicate elements unnecessarily.
The iteration is faster too for the same reason.
Actually if there were duplicates it would be a lot tougher problem to solve.

The only way I see to make it faster won't be possible in \$O(1)\$ space:
instead of sorting the first list, you could put it in a hash set.
That way the binary search becomes a hash lookup, which is much faster,
but at the expense of doubling the memory usage of one of the lists.

When you have two lists of very different sizes,
I'm wondering if it can be said that making the shortest to be the first or the second will yield better performance in general.