miMerge.
Este algoritmo iterativo está inspirado en Merge Sort de Von Neuman.
La idea básica es que Merge Sort no aprovecha el orden intrínseco de cualquier vector desordenado (como mínimo los elementos estarán ordenados de dos en dos).
Los objetivos (que no sé si he alcanzado, porque son ideales), són:
-Un algoritmo que aproveche al máximo el orden existente en un vector dado.
-Ordenación en N para un vector ya ordenado, ordenación en 2N para un vector ordenado en orden inverso.
-Ordenación en n log n para el peor caso.
-Numero de comparaciones mínimo, exactamente igual al de mergesort.
Como se ve, estos dos últimos son los más difíciles (de hecho supongo que el número de comparaciones de mergesort no es mínimo).
Como aún no he visto ningún algoritmo de este estilo propongo el mío.
Se buscan los (i-a+1) primeros elementos ordenados (en orden creciente o inverso), luego los siguientes (i-a+1) elementos ordenados y se mezclan los dos vectores ordenados para formar un vector resultado, ordenado en orden creciente, se continua de la misma forma, mezclando los siguientes (i-a+1) elementos ordenados con el vector resultado precedente.
a será por lo tanto el indice del primer elemento de un trozo de vector ordenado, e i el indice del último elemento de ese mismo trozo de vector ordenado
algoritmo miMerge (v: ES vector) es
orden:bool;
a,i:tpIndice;
ppio
i:=1;
a:=i;
orden:=directo;
mQ no i>=DIM(v)
si v[i]<v[i+1]
si orden = directo
sigue;
si_no –orden =inverso
mergeInvirtiendo(a,i);
orden:=directo;
a:=i+1;
fSi;
si_no — v[i]>=v[i+1]
si orden = directo
merge(a,i);
orden:=inverso;
a:=i+1;
si_no –orden =inverso
sigue;
fSi;
fSi;
i:=i+1;
fMQ;
fin;
P.D.: Sí el algoritmo está mal, o su coste en el peor caso es N!, que nadie me tiré una piedra a la cabeza, con explicarme lo que está mal e intentar optimizarlo valdría.
P.D.2:Después del Paso De Ecuador escribo mergeInvirtiendo y merge :P. Adelanto que mergeInvirtiendo, invierte y luego mezcla.