Fredman [Fre76] proved that if a given partial order on m elements has L linear extensions, then the set can be sorted in at most log_{2}L + 2m comparisons. For the sorting X + Y problem, we have m = n^{2}, the Hasse diagram of the partial order is an n×n diagonal grid, and simple arguments about hyperplane arrangements imply that L = O(n^{8n}). Thus, Fredman's algorithm can sort X + Y using only 8n log n + 2n^{2} comparisons; unfortunately, the algorithm needs exponential time to choose which comparisons to perform! This exponential overhead was reduced to polynomial time by Kahn and Kim [KK95] and then to O(n^{2}log n) by Lambert [Lam92] and Steiger and Streinu [SS95]. These results imply that no superquadratic lower bound is possible in the full linear decision tree model.
If the input consists of n integers between - M and M, an algorithm of Seidel based on fast Fourier transforms runs in O(n + M log M) time [Eri99a]. The Ω(n^{2}) lower bounds require exponentially large integers.
A closely related problem does have a subquadratic solution: find a minimum element of X + Y, the so-called min-convolution problem, posed by Jeff Erickson [DO06]. See [BCD+06] for the result and a discussion of connections to the sorting problem.