Que es un conjunto de llegada

TF:1

Asumiendo que se permita usar almacenamiento extra, ejecutar la comparación como un torneo de eliminación simple, manteniendo un registro de las entradas derrotadas por cada ganador en el camino. (Número bajo gana). Cuando se obtiene un ganador total, solo hay que identificar al ganador entre τlgnτconncursantes superados por el ganador general.
Revisando esto, no se necesita memoria adicional, si uno reorganiza la lista. Implementar el torneo de eliminación simple de la siguiente manera:

Suponer que los números son a₀, a₁,..., a_n-1 . En la primera pasada comparar  con para ; si , intercambiarlos. En la segunda pasada comparar  con  para  ; si , intercambiar el par  con el par . En la i-esima pasada comparar  con para ; si , intercambiar los bloques de longitud  empezando en  y . Esto continua mientras , por ejemplo, hasta ; por lo tanto, si la última pasada es la m-ésima pasada, entonces , o . El número más pequeño en el conjunto es ahora a₀, y cada otro número en el conjunto ha perdido exactamente una comparación, por lo que se han hecho n-1 comparaciones.

 Los números que ahora son  para i=0,...,m-1 son los números que perdieron a a₀ en las comparaciones directas; cada número en el conjunto que no es a₀ ni uno de estos m números pierde una comparación directa con uno de estos m números y por lo tanto no puede ser el segundo número más pequeño en el conjunto. Por lo tanto, el segundo número más pequeño es el más pequeño de los  para i=0,...,m-1. Hay m de estos números, por lo que se necesitan m-1 comparaciones para encontrar el más pequeño. Todo el algoritmo en conjunto toma:

comparaciones