Find pair of complex numbers with maximal sum
Observations:


The pairing mechanism creates the Minkowski sum of the two sets.
The convex hull of the Minkowski sum is the Minkowski sum of the convex hulls. (See e.g. previously linked Wikipedia article).
Given a set of points in the plane, the point furthest from the origin must be a vertex of the convex hull.
The convex hull of a set of $n$ points can be found in $O(n \lg n)$ time. (In fact in $O(n \lg h)$ time, where $h$ is the number of points on the convex hull).

  For two convex polygons P and Q in the plane with $m$ and $n$ vertices, their Minkowski sum is a convex polygon with at most $m + n$ vertices and may be computed in time $O(m + n)$ by a very simple procedure...


given in the Wikipedia article.


Combining these observations gives an $O(n \lg n)$ algorithm.