Generalizando un poco más.
Ordenar N elementos será igual que ordenar N vectores ordenados de un elemento.Esta operación es la fusión de vectores (merge), y conseguir el merge óptimo de N vectores ordenados sería equivalente al algoritmo de ordenación óptimo.De momento sabemos la forma de buscar un elemento en un vector, pero lo que necesitamos es el merge de dos vectores.Por lo tanto intentemos generalizar el algoritmo de búsqueda binaria, para dos vectores. El mejor algoritmo de merge conocido hasta el momento es muy simple, y dados dos vectores de a y b elementos respectivamente, siempre hace a+b-1 comparaciones.Evidentemente ese algoritmo no es el que buscamos, pero nos dará una cota de lo que buscamos que sea el peor caso para el merge de dos vectores.
Empecemos. Tenemos dos vectores, v1 y v2
v1: |1|2|3|4|5|6|7|8|9|v2:|1|2|3|4|5|6|7|8|9|
Como queremos generalizar la búsqueda binaria, lo que es evidente es que la primera comparación a realizar será comparar los dos centros. 5<=5Tras ello, querremos situar uno de los dos centros comparados dentro del otro vector. La elección igual que con el redondeo en búsqueda binaria, no parece tener mucha importancia. Por las mismas razones que antes, elegiremos el primer centro de los dos. Este elemento será nuestro pivote, para esta iteración del algoritmo.Por lo tanto:
v1: |1|2|3|4|5|6|7|8|9|v2:|1|2|3|4|
5>2
v1: |1|2|3|4|5|6|7|8|9|v2:|3|4|
5>3
v1: |1|2|3|4|5|6|7|8|9|v2:|4|
5>4
Por lo tanto, tenemos la posición del elemento central del primer vector en el segundo. Es decir, hemos separado los datos de la forma siguiente.
|1|2|3|4| |5| |6|7|8|9|
|1|2|3|4| |5|6|7|8|9|
Podemos repetir la operación recursivamente, para los vectores que nos quedan a la izquierda de nuestro pivote por un lado, y para los vectores que nos quedan a la derecha de nuestro pivote por el otro.
Ya tenemos un algoritmo de merge de dos vectores, óptimo en el número de comparaciones.
Como prueba de que no me equivoco, el numero de comparaciones siempre es igual o inferior al del merge clásico (a+b-1 para dos vectores de tamaño a y b).