Una idea para empezar.
Intuitivamente, creo que un algoritmo óptimo de ordenación por comparación, será una generalización de la búsqueda binaría.¿Porqué?Porque la búsqueda binaría es el algoritmo óptimo de búsqueda la posición de un elemento entre otros elementos ordenados. Esto se debe a que si tenemos N elementos ordenados, y como única operación la comparación, la operación que más información nos dará será siempre comparar con el elemento central, de esta forma a cada paso descartamos la mitad de los elementos a comparar.
Por ejemplo, si buscamos la posición el dato D en el vector V:
i) V= |1|2|3|4|5|6|7|8|9 | D=6
Nuestra primera comparación será preferentemente 5<=6, ya que 5 es el elemento central del vector. Así, descartamos las comparaciones con los elementos anteriores al 5 (y con el 5).
ii) V1= |6|7|8|9| D=6
Al quedar un número par de elementos, podemos elegir entre el redondeo a la izquierda o a al derecha, en terminos de valor medio, ambas elecciones resultan en la misma cantidad de comparaciones, sin embargo, en los computadores, las cachés hacen que en general los accesos secuenciales, de izquierda a derecha sean más rápidos. Aunque puede que eso no suponga una diferencia significativa, lo que es evidente es que no va a resultar peor.Por lo tanto la comparación será 7>6, con lo que descartamos todos los elementos superiores al 7, y el 7.
iii) V2= |6| D=6
Comparamos 6<=6, por lo tanto tenemos el vector |6|6| ordenado.Lo juntamos con los “trozos” de vectores que hemos ido descartando, y nos da el resultado |1|2|3|4|5|6|6|7|8|9 |
Una pequeña puntualizacion. Esto es cierto porque hemos definido como óptimo, que sea óptimo en comparaciones, si nos saltasemos esa regla, esta misma operación de búsqueda podría hacerse mucho más rápido.La búsqueda binaría hace Log2(n) comparaciones para situar un dato , sin embargo, con una búsqueda interpolatoria lineal, las comparaciones en el caso medio, pasarían a ser log2 log2 (n), mucho más rápido, pero aquí ya no se usa únicamente la operación de comparación, sino también el valor del dato. Creo que el limite estaría en usar una función interpolatoria de todos los datos ordenados, y hayar la posición de forma directa en tiempo constante.Puede que mediante interpolación se puedan ordenar n elementos en O(n), pero eso se sale de mis objetivos actuales, que ya de por si son muy ambiciosos, y requiere una gran habilidad matemática.