ELO Rating as a sorting algorithm Let $N$ be the number of players each with a true rating $R_i$, where $i \in \{1,2,...,N\}$. Two players, $A$ and $B$, are selected at random and made to play a game. Let their current ratings be $R_A$ and $R_B$, respectively. We use the ELO rating system to calculate the expectation of a player to win the game as
$$E_A = \frac{1}{1 + 10^{(R_B - R_A)/400}}, \\
E_B = \frac{1}{1 + 10^{(R_A - R_B)/400}}.$$
Their new ratings are given by the expressions
$$R'_A = R_A + K(S_A - E_A),\\
R'_B = R_B + K(S_B - E_B).$$
If $A/B$ wins, $S_{A/B} = 1$. If $A/B$ loses, $S_{A/B} = 0$. $K$ is a constant (say 32). If each of these $N$ players start with a base rating of 1400, what order of games are required for the players to arrive at an accurate ranking? More generally, how does ELO rating serve as a sorting algorithm?
 A: As the comments have noted, this question isn't quite well specified, so allow me to make a few specifications to the problem.
Let's say that there is a positive lower bound $\epsilon$ on the differences between true Elo scores. This is convenient because otherwise, it might take an arbitrarily long time to statistically determine which of two players is better, even if every game played were between them.
Unfortunately, even with this assumption, it seems it is not the case that the probability that the ratings are correctly sorted approaches one as the number of games played increases. Even if all the players scores are exactly correct at some point, if we play further games, there is a non-zero chance that one player will win disproportionately to how often they are expected to, and the sorting could change.
Instead, I think it's interesting to consider another approach, where instead of tracking and updating an estimate of a players scores, we instead simply estimate the sorted list of players at any given time, perhaps by a maximum likelihood estimate of the Elo scores, or some other function of the records of each player.
In the usual lower bound on the runtime of sorting algorithms, we observe that each comparison gives us 1 bit of information about the true order, and that this means at least $O(\log_2 n!) = O(n \log n)$ comparisons are necessary to correctly sort the list. In our scenario, each game gives less than 1 bit, so at least $O(n \log n)$ games will still be necessary to achieve any constant probability of correctness.
On the other hand, there are algorithms that sort in $n \log n$ time. If we imagine playing $k_{\epsilon, n, p}$ games between a pair of players whenever we would compare them, where $k_{\epsilon, n, p}$ is large enough to guarantee a less than $\frac{p}{n \log n}$ chance that the worse player wins more often, then we would have probability less than $p$ of any of the comparisons getting it wrong. Thus, we could get we could sort the players accurately in $O(k_{\epsilon, n, p} n \log n)$. Keeping $\epsilon, p$ constant, $k$ should be roughly quadratic in $n$, so I bet you could sort the players in $\tilde{O}(n^3)$ games, maybe less with something more clever.
