I mean that needing to scan the full context of tokens before the nth is inherent to the problem of sorting. Transformers do scan that input, which is good; it's not surprising that they're up to the task. But pairwise numeral correlations will not do the job.

As for avoiding certain cases, that could be done to some extent. But remember that the untrained transformer has no preconception of numbers or ordering (it doesn't use the hardware ALU or integer data type) so there has to be enough data in the training set to learn 0<1<2<3<4<5<6, etc.