Decide existence of total orderings
Pyth, 28 22
L.AmqdSdmfhTmxhkbek^b2

Creates a function y that you can call with a tuple containing the two arrays. Returns &quot;True&quot; if a total ordering exists, &quot;False&quot; if not.
A helper program that defines and calls the above function with stdin:
L.AmqdSdmfhTmxhkbek^b2y,rw7rw7 

Try it here.
We first read both arrays. Then we will create all combinations of both arrays. Then for each combination we will assume the first array is authoritative, and check if it's consistent with the second array.