ordenación por fusión e inserción

En informática , el algoritmo de ordenación por inserción-fusión o algoritmo de Ford-Johnson es un algoritmo de ordenación por comparación publicado en 1959 por LR Ford Jr. y Selmer M. Johnson . ^{[ 1 ] [ 2 ] [ 3 ] [ 4 ]} Utiliza menos comparaciones en el peor de los casos que los mejores algoritmos conocidos hasta entonces, la ordenación por inserción binaria y la ordenación por fusión , ^{[ 1 ]} y durante 20 años fue el algoritmo de ordenación con el menor número de comparaciones conocido. ^{[ 5 ]} Aunque no tiene relevancia práctica, sigue siendo de interés teórico en relación con el problema de la ordenación con un número mínimo de comparaciones. ^{[ 3 ]} Es posible que el mismo algoritmo también haya sido descubierto independientemente por Stanisław Trybuła y Czen Ping. ^{[ 4 ]}

La ordenación por fusión e inserción realiza los siguientes pasos en una entrada.${\displaystyle X}$de${\displaystyle n}$elementos: ^{[ 6 ]}

1. Agrupa los elementos de${\displaystyle X}$en${\displaystyle \lfloor n/2\rfloor }$pares de elementos, arbitrariamente, dejando un elemento sin emparejar si hay un número impar de elementos.
2. Llevar a cabo${\displaystyle \lfloor n/2\rfloor }$comparaciones, una por par, para determinar el mayor de los dos elementos en cada par.
3. Ordenar recursivamente el${\displaystyle \lfloor n/2\rfloor }$elementos más grandes de cada par, creando una secuencia ordenada${\displaystyle S}$de${\displaystyle \lfloor n/2\rfloor }$de los elementos de entrada, en orden ascendente, utilizando el algoritmo de ordenación por fusión e inserción.
4. Insertar al inicio de${\displaystyle S}$el elemento que se emparejó con el primer y más pequeño elemento de${\displaystyle S}$.
5. Inserta el resto${\displaystyle \lceil n/2\rceil -1}$elementos de${\displaystyle X\setminus S}$en${\displaystyle S}$, uno a la vez, con un orden de inserción especialmente elegido que se describe a continuación. Utilice la búsqueda binaria en subsecuencias de${\displaystyle S}$(como se describe a continuación) para determinar la posición en la que se debe insertar cada elemento.

El algoritmo está diseñado para aprovechar el hecho de que las búsquedas binarias utilizadas para insertar elementos en${\displaystyle S}$son más eficientes (desde el punto de vista del análisis del peor caso) cuando la longitud de la subsecuencia que se busca es uno menos que una potencia de dos . Esto se debe a que, para esas longitudes, todos los resultados de la búsqueda utilizan el mismo número de comparaciones entre sí. ^{[ 1 ]} Para elegir un orden de inserción que produzca estas longitudes, considere la secuencia ordenada${\displaystyle S}$después del paso 4 del esquema anterior (antes de insertar los elementos restantes), y dejar${\displaystyle x_{i}}$denotan el${\displaystyle i}$el enésimo elemento de esta secuencia ordenada. Por lo tanto,

${\displaystyle S=(x_{1},x_{2},x_{3},\dots ),}$

donde cada elemento${\displaystyle x_{i}}$con${\displaystyle i\geq 3}$está emparejado con un elemento${\displaystyle y_{i}<x_{i}}$que aún no se ha insertado. (No hay elementos${\displaystyle y_{1}}$o${\displaystyle y_{2}}$porque${\displaystyle x_{1}}$y${\displaystyle x_{2}}$estaban emparejados entre sí.) Si${\displaystyle n}$es extraño, el elemento no emparejado restante también debe numerarse como${\displaystyle y_{i}}$con${\displaystyle i}$mayor que los índices de los elementos emparejados. Entonces, el paso final del esquema anterior se puede expandir en los siguientes pasos: ^{[ 1 ] [ 2 ] [ 3 ] [ 4 ]}

• Dividir los elementos no insertados${\displaystyle y_{i}}$en grupos con índices contiguos. Hay dos elementos${\displaystyle y_{3}}$y${\displaystyle y_{4}}$En el primer grupo, y la suma de los tamaños de cada dos grupos adyacentes forma una secuencia de potencias de dos. Por lo tanto, los tamaños de los grupos son: 2, 2, 6, 10, 22, 42, ...
• Ordena los elementos no insertados por sus grupos (índices más pequeños a índices más grandes), pero dentro de cada grupo ordénalos de índices más grandes a índices más pequeños. Por lo tanto, el orden se convierte en:

${\ Displaystyle y_ {4},y_ {3},y_ {6},y_ {5},y_ {12},y_ {11},y_ {10},y_ {9},y_ {8},y_ {7},y_ {22},y_ {21}\dots}$

• Utilice este orden para insertar los elementos.${\displaystyle y_{i}}$en${\displaystyle S}$. Para cada elemento${\displaystyle y_{i}}$, utilice una búsqueda binaria desde el principio de${\displaystyle S}$hasta pero sin incluir${\displaystyle x_{i}}$para determinar dónde insertar${\displaystyle y_{i}}$.

Dejar${\displaystyle C(n)}$denota el número de comparaciones que realiza el ordenamiento de fusión-inserción, en el peor de los casos, al ordenar${\displaystyle n}$elementos. Este número de comparaciones se puede desglosar como la suma de tres términos:

• ${\displaystyle \lfloor n/2\rfloor }$comparaciones entre pares de elementos,
• ${\displaystyle C(\lfloor n/2\rfloor )}$comparaciones para la llamada recursiva y
• cierto número de comparaciones para las inserciones binarias utilizadas para insertar los elementos restantes.

En el tercer término, el número de comparaciones en el peor de los casos para los elementos del primer grupo es dos, porque cada uno se inserta en una subsecuencia de${\displaystyle S}$de longitud como máximo tres. Primero,${\displaystyle y_{4}}$se inserta en la subsecuencia de tres elementos${\displaystyle (x_{1},x_{2},x_{3})}$. Entonces,${\displaystyle y_{3}}$se inserta en alguna permutación de la subsecuencia de tres elementos${\displaystyle (x_{1},x_{2},y_{4})}$, o en algunos casos en la subsecuencia de dos elementos${\displaystyle (x_{1},x_{2})}$. De manera similar, los elementos${\displaystyle y_{6}}$y${\displaystyle y_{5}}$de los del segundo grupo se insertan cada uno en una subsecuencia de longitud como máximo siete, utilizando tres comparaciones. De manera más general, el número de comparaciones en el peor de los casos para los elementos en el${\displaystyle i}$el grupo es${\displaystyle i+1}$, porque cada uno se inserta en una subsecuencia de longitud como máximo${\displaystyle 2^{i+1}-1}$. ^{[ 1 ] [ 2 ] [ 3 ] [ 4 ]} Sumando el número de comparaciones utilizadas para todos los elementos y resolviendo la relación de recurrencia resultante , este análisis puede utilizarse para calcular los valores de${\displaystyle C(n)}$, dando la fórmula ^{[ 7 ]}

${\displaystyle C(n)=\sum _{i=1}^{n}\left\lceil \log _{2}{\frac {3i}{4}}\right\rceil \approx n\log _{2}n-1.415n}$

o, en forma cerrada , ^{[ 8 ]}

${\displaystyle C(n)=n{\biggl \lceil }\log _{2}{\frac {3n}{4}}{\biggr \rceil }-{\biggl \lfloor }{\frac {2^{\lfloor \log _{2}6n\rfloor }}{3}}{\biggr \rfloor }+{\biggl \lfloor }{\frac {\log _{2}6n}{2}}{\biggr \rfloor }.}$

Para${\displaystyle n=1,2,\dots }$El número de comparaciones es ^{[ 1 ]}

0, 1, 3, 5, 7, 10, 13, 16, 19, 22, 26, 30, 34, ... (secuencia A001768 en el OEIS )

El algoritmo se denomina ordenación por fusión e inserción porque las comparaciones iniciales que realiza antes de su llamada recursiva (emparejar elementos arbitrarios y comparar cada par) son las mismas que las comparaciones iniciales de la ordenación por fusión , mientras que las comparaciones que realiza después de la llamada recursiva (utilizar la búsqueda binaria para insertar elementos uno a uno en una lista ordenada) siguen el mismo principio que la ordenación por inserción . En este sentido, es un algoritmo híbrido que combina la ordenación por fusión y la ordenación por inserción. ^{[ 9 ]}

Para entradas pequeñas (hasta${\displaystyle n=11}$) su número de comparaciones es igual al límite inferior de la ordenación por comparación de${\displaystyle \lceil \log _{2}n!\rceil \approx n\log _{2}n-1.443n}$Sin embargo, para entradas más grandes, el número de comparaciones realizadas por el algoritmo de fusión-inserción es mayor que este límite inferior. La ordenación por fusión-inserción también realiza menos comparaciones que los números de ordenación , que cuentan las comparaciones realizadas por la ordenación por inserción binaria o la ordenación por fusión en el peor de los casos. Los números de ordenación fluctúan entre${\displaystyle n\log _{2}n-0.915n}$y${\displaystyle n\log _{2}nn}$, con el mismo término principal pero un factor constante peor en el término lineal de orden inferior. ^{[ 1 ]}

El algoritmo de ordenación por fusión e inserción es el algoritmo de ordenación con el mínimo número posible de comparaciones para${\displaystyle n}$artículos cuando${\displaystyle n\leq 22}$y tiene la menor cantidad de comparaciones conocidas para${\displaystyle n\leq 46}$. ^{[ 10 ] [ 11 ]} Durante 20 años, el algoritmo de ordenación por fusión e inserción fue el algoritmo de ordenación con el menor número de comparaciones conocido para todas las longitudes de entrada. Sin embargo, en 1979 Glenn Manacher publicó otro algoritmo de ordenación que utilizaba aún menos comparaciones, para entradas suficientemente grandes. ^{[ 3 ] [ 5 ]} Sigue siendo desconocido exactamente cuántas comparaciones se necesitan para la ordenación, para todas${\displaystyle n}$, pero el algoritmo de Manacher y los algoritmos de ordenación posteriores que batieron récords han utilizado modificaciones de las ideas de ordenación por fusión e inserción. ^{[ 3 ]}