El algoritmo de ordenación de vectores Fusión, fue desarrollado por John Von Neumann en 1.945 con la denominación de Merge Sort. Recordamos que Neumann fue un 
gran colaborador de la CIA y la mente pensante de EE.UU. en los aspectos científicos de la guerra fría y de la bomba atómica. Murió joven, por cáncer, probablemente por su afición a las pruebas atómicas.
El algoritmo sigue la idea del divide y vencerás, y en la actualidad puede ejecutarse en paralelo obteniendo todos los beneficios de los procesadores actuales. Algo que parece en contra es el incremento del consumo de memoria debido a la recursividad, pero el nivel de recursión está limitado por log2 (n), por lo que no son posibles las pilas profundas.
| Rendimiento – Complejidad | |||
| Mejor caso Ω | Peor caso O | Media Θ | Espacio |
| (n log n) | (n log n) | (n log n) | O(n) |
Tipos.
En el gráfico se muestran a “grosso modo”, los distintos tipos que existen del modo de operación del método de Fusión. Según ha ido pasando el tiempo se han entrelazado los algoritmos que suministraban una solución única y en algunos casos es difícil desmenuzar sus relaciones. La fusión de 2 direcciones o binaria es la más utilizada.
Versión Interna Recursiva.
Este algoritmo trabaja de la siguiente forma:
- Dividimos el vector en dos sub-vectores.
- Recursivamente tomamos los subvectores y dividimos cada uno de ellos en otros dos (izquierda – derecha) o (menor-mayor) hasta que solo quede un elemento para realizar la división.
- Al terminar la división se fusionan los subvectores (divisiones) desde su inicio. Tomamos el elemento que es menor y lo colocamos en el nuevo vector, para este vector seleccionamos los siguientes elementos y tomamos el elemento menor de ambos vectores (comparamos a la vez un elemento de cada vector).
- Si hubiese quedado pendiente algún elemento se repasan los vectores izquierda y derecha.
En algunas ocasiones se la denomina: fusión de arriba hacia abajo.
Versión Interna Iterativa.
También denominada de abajo hacia arriba, utiliza un enfoque ascendente, en el ejemplo se ordenan los vectores de tamaño 1 y se fusionan en sub-vectores de 2 elementos, repetimos la operación y se fusionan en sub-vectores de 4 elementos y así sucesivamente ( 8, 16, …) .
Vesión Interna Multihilo.
Después de una noche de fiesta no se me ocurre otra cosa que tratar de mejorar el tiempo de ejecución.
En el ejemplo he dividido (si el resultado no es entero-par modificar el programa) el vector de 38M con valores de 1 a 100M, en 4 subvectores que clasifico con 4 hilos, concateno el resultado y finalmente lo ordeno. De 8,3 segundos en la versión recursiva, pasa a 7,2 segundos.
Estadísticas.
En las pruebas se ha incluido la versión de Sedgwick-Wayne, existen muchas más pero con estas es suficiente para darnos cuenta de sus diferencias. Estadística individual realizada con el mismo equipo y condiciones del resumen de estadísticas de ordenación.
