O((n1 + n2) * log(n2)) looks better to me than O(n1 * n2), I don't know if I am missing something here. It does depend on the relative lengths of n1 and n2 though.

Technically, his solution is more optimal than the other solutions given. If you use qsort (O(n2 log n2) on the avg. case) on arr2, and bsort on arr2 for every element in arr1 ((O(n1 log n2)), then you have a time complexity of O((n1 + n2) * log(n2)), while the complexity of the other solutions are O(n1 * n2).

Every solution I've seen in here is O(n^2), safe to say I don't think there's a better way of doing it (You're calling qsort() once and then bsearch() on every iteration, not sure whether that's O(n^2) or not tbh)