Mergesort

Mergesort

Este método de ordenamiento toma la lista de llaves y la divide en dos partes, las cuales se ordenan en forma independiente. Finalmente, las dos listas ordenadas resultantes, se mezclan para formar la lista ordenada final.

EJEMPLO:

Realicemos el seguimiento para una lista con los siguientes datos:

7 – 5 – 3 – 9 – 8 – 2 – 6 – 1

La lista de llaves se divide en 2 partes iguales,

Lista1: 7 – 5 – 3 – 9
Lista2: 8 – 2 – 6 – 1

Aplicamos el método de ordenamiento nuevamente para cada una de las listas:

Análisis del Algoritmo:

• Mejor Caso: O(n log n)
• Peor Caso: O(n log n)
• Caso Promedio: O(n log n)