MERGE SORT

Este algoritmo tambien es llamado de intercanbio o combinacion, debido que combina (intercala) dos estructuras previamente ordenadas.

Este algoritmo consiste en:

- Dividir el grupo de datos en dos y ordenar por separado cada mitad.

- Cuando se tengan las mitades ordenadas, pueden irse mezclando para obtener fácilmente una secuencia ordenada.

El algoritmo MergeSort Utiliza los siguientes tres pasos:

DIVIDIR: divide la secuencia de "n" elementos a ordenar en dos subsecuencias de "n/2" elementos cada una.
VENCER: ordena las dos subsecuencias de manera recursiva mediante el algoritmo MERGESORT.
COMBINAR: combina las dos subsecuencias ordenadas para generar la solución.

De ahí su comparación con el paradigma algorítmico: "Divide y Vencerás".



Este algoritmo fue desarrollado por el matemático húngaro John Von Neumann en 1945.

[Thomas Cormen, 2001].