Lower Bound for Time Complexity of Pairing Problem

Question

Given an array X and array Y both of length n, the pairing algorithm will return the elements of the arrays matched so that the smallest element in X will be matched with the smallest element of Y, the second smallest in X matched with second smallest in Y and so on. i.e the algorithm will yield the pairs: $(x_{1},y_{1}),...,(x_{i},y_{i}),...,(x_{n},y_{n})$, $x_{i}$ being the i'th smallest element in X.
I need to find the lower bound for the time complexity of the problem.

I think the lower bound is O(n) because when the two arrays are sorted we only need to match the elements with the same index in each array - so we'll need to go over n indices = O(n). But this just proves the existence of the possible time complexity of O(n) and doesn't prove it's the minimum.

Is O(n) the lower bound? And if so what is the proof?