Axiom, 439 bytes
c:=0;s(x,y)==(free c;if x.1=%i and y.2=%i then(x.2<y.1=>return true;x.2>y.1=>return false;c:=1;return false);if x.2=%i and y.1=%i then(x.1<y.2=>return true;x.1>y.2=>return false;c:=1;return false);if x.1=%i and y.1=%i then(x.2<y.2=>return true;x.2>=y.2=>return false);if x.2=%i and y.2=%i then(x.1<y.1=>return true;x.1>=y.1=>return false);false);r(a,b)==(free c;c:=0;m:=[[%i,j] for j in a];n:=[[i,%i] for i in b];r:=merge(m,n);sort(s,r);c)
this convert the first list in a list as [[i,1], [i,2]...] the second list in a list as [[1,i], [0,i]...]
where i is the variable imaginary
than merge the 2 list, and make one sort that would find if there is one element of list 1 in the list 2
so it is at last O(N log N) where N=lenght list 1 + lenght list 2
ungolfed
-- i get [0,0,1,2,3] and [0,4,6,7] and build [[%i,0],[%i,0],[%i,1],[%i,2] [%i,3],[0,%i],..[7,%i]]
c:=0
s(x:List Complex INT,y:List Complex INT):Boolean==
free c -- [%i,n]<[n,%i]
if x.1=%i and y.2=%i then
x.2<y.1=> return true
x.2>y.1=> return false
c:=1
return false
if x.2=%i and y.1=%i then
x.1<y.2=>return true
x.1>y.2=>return false
c:=1
return false
if x.1=%i and y.1=%i then
x.2< y.2=>return true
x.2>=y.2=>return false
if x.2=%i and y.2=%i then
x.1< y.1=>return true
x.1>=y.1=>return false
false
r(a,b)==
free c
c:=0
m:=[[%i, j] for j in a]
n:=[[ i,%i] for i in b]
r:=merge(m,n)
sort(s, r)
c
results
(12) -> r([1,2,3,4,-5], [5,7,6,8]), r([],[0]), r([],[]), r([1,2],[3,3]), r([3,2,1],[-4,3,5,6]), r([2,3],[2,2])
Compiling function r with type (List PositiveInteger,List Integer)
-> NonNegativeInteger
Compiled code for r has been cleared.
Compiled code for s has been cleared.
Compiling function r with type (List PositiveInteger,List
PositiveInteger) -> NonNegativeInteger
Compiled code for r has been cleared.
Compiling function s with type (List Complex Integer,List Complex
Integer) -> Boolean
Compiled code for s has been cleared.
(12) [0,0,0,0,1,1]
Type: Tuple NonNegativeInteger
i dont understand why it "clears" code for r and s...
O(n log n)
is doable in general, but the clarification about only handling native integers means that in some languages with limited integer ranges a linear solution is possible (e.g. by a 2^64 size lookup table) \$\endgroup\$