## An Efficient Sorting Algorithm for a Sequence of Kings in a Tournament

### Authors: Jie Wu and Li Sheng

ABSTRACT

A king $u$ in a tournament is a player who beats ($\rightarrow$) any other player $v$ {\em directly or indirectly}. That is, either $u \rightarrow v$ or there exists a third player $w$ such that $u \rightarrow w$ and $w \rightarrow v$. A sorting sequence of kings in a tournament of $n$ players is a sequence of players, $S=(u_1$, $u_2$, ..., $u_n)$, such that $u_i \rightarrow u_{i+1}$ and $u_i$ in a king in the sub-tournament $T_{u_i}$ induced by $u_i, u_{i+1}, ..., u_n$ for $i=1, 2,..., n-1$. The existence of a sorting sequence of kings in any tournament is shown \cite{LouW00} where a sorting algorithm with a complexity of $\Theta(n^{3})$ is given. In this paper, we present a constructive proof for the existence of a sorting sequence of kings of a tournament and propose an efficient algorithm with a complexity of $\Theta(n^2)$.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2000/2000-12.ps.gz