Parity of a Permutation
MATL, 17 16 bytes
1 byte removed thanks to a suggestion by Dennis
2$St!&lt;Rz2\'oe'w)

This works in current version (15.0.0) of the language.
Try it online!
Explanation
This uses the definition of parity in terms of inversions. An inversion is a pair of elements in the second array that are in the &quot;wrong&quot; order compared with the first array. Since the first array need not be sorted, we first sort it and the same rearrangement needed for that sorting is applied to the second array. Then an inversion corresponds to a pair of elements that is not increasing in the second array.
Note also that the two input arrays can be swapped and the result is the same. So it's not important which array is considered to be the &quot;original&quot; and which the &quot;permuted&quot;.
2$S     % implicitly take two row vectors. Sort second and apply the indices
        % of that sorting to the first
t!      % duplicate. Transpose into column vector
&lt;       % true for elements of the column vector that exceed those of the 
        % row vector. Gives a 2D array with all pairs of comparisons
R       % keep only upper triangular part of that array
z       % number of nonzero elements. This is the number of inversions
2\      % parity of that number: gives 0 or 1
'oe'w   % push string 'eo' below the top of the stack
)       % apply index to produce 'e' or 'o'. An index 1 refers to the first
        % element, whereas 0 refers to the last. Implicitly display