Lower Bound for Time Complexity of Pairing Problem
This answer uses the convention that the elements of $X$ are $x_1,\ldots,x_n$ (in their original, unsorted order), and similarly the elements of $Y$ are $y_1,\ldots,y_n$. This differs from your convention.



The complexity of this problem in the comparison model (as well as in related models, such as bounded degree algebraic decision trees) is $\Theta(n\log n)$.

For the upper bound, we can solve the problem by sorting both lists.

For the lower bound, if we fix the second array to be $y_i = i$, then we are essentially sorting the first array $X$. Stated differently, there is a reduction from sorting to this problem, with the same value of $n$ and no extra comparisons. Since sorting takes $\Omega(n\log n)$ comparisons in the worst case, this problem also requires $\Omega(n\log n)$ comparisons.



So far we have only discussed worst-case complexity, and the same argument also works for average-case complexity. The best-case complexity is $\Theta(n)$. This means that we can find a correct algorithm that runs in time $O(n)$ on some input; and every correct algorithm requires $\Omega(n)$ comparisons on every input.

For the upper bound, consider the algorithm that first checks whether both $X$ and $Y$ are increasing ($2(n-1)$ comparisons). If so, it returns the mapping $(x_i,y_i)$. Otherwise, it transfers control to an arbitrary correct algorithm.

The lower bound follows from the same reduction from sorting, since sorting is known to require at least $n-1$ comparisons on any input. Indeed, the same argument used to prove this shows that any algorithm for the pairing problem requires $2(n-1)$ comparisons on any input.