Sobre el algoritmo anterior.
Explicándolo de forma sencilla; ordenar n datos es lo mismo que poner el dato mínimo en la posición inferior, el máximo en la posición superior y repetir el algoritmo para n-2 datos.
O lo que es lo mismo 1/2(n^2-n) = 1 + 2(n-1) + 1/2((n-2)^2-(n-2).
Tambien podría hacerse 1/2(n^2-n)= n-1 + 1/2((n-1)^2-(n-1)), que de hecho es el algoritmo de selección.
Así que he reinventado la rueda :P. El algoritmo es un cocktail sort por selección recursivo.
P.D.: ¿Pero a que queda bonito simétrico y recursivo?