This depends on your model of computation. If you only allow arithmetic and comparisons (the algebraic decision tree model) then there is an $\Omega(n\log n)$ lower bound for element distinctness, the problem of deciding whether all elements are distinct. Your problem is of course even harder, so the same lower bound applies.
(There is some fine print: the lower bound only holds if the degree of the polynomials being compared is bounded. If all you're doing is comparing various differences $x_i - x_j$, then you're good to go. The algebraic decision tree model also allows you to compare more general polynomials in the inputs, as long as they have bounded degree.)
There are other models which might perform better — for example, in some models you can sort integers in $o(n\log n)$. But I imagine you don't want to allow the sort of trickery used in such algorithms.