To sort $S$, do a radix sort on the bits of each of the $n$ elements, viewing them as pairs $(i,j)$ such that $i$ and $j$ are integers in the range $[0,n-1]$.