  In his study of Kazhdan-Lusztig cells in affine type $A$, Shi has introduced
an affine analog of Robinson-Schensted correspondence. We generalize the
Matrix-Ball Construction of Viennot and Fulton to give a more combinatorial
realization of Shi's algorithm. As a biproduct, we also give a way to realize
the affine correspondence via the usual Robinson-Schensted bumping algorithm.
Next, inspired by Lusztig and Xi, we extend the algorithm to a bijection
between extended affine symmetric group and triples $(P, Q, \rho)$ where $P$
and $Q$ are tabloids and $\rho$ is a dominant weight. The weights $\rho$ get a
natural interpretation in terms of the Affine Matrix-Ball Construction.
Finally, we prove that fibers of the inverse map possess a Weyl group symmetry,
explaining the dominance condition on weights.
