Merge Sort

Problema:

Dado un arreglo desordenado de números, hallar el arreglo ordenado.

Ejemplos:

Entrada: 1 -20 1998 0 42; Salida: -20 0 1 42 1998

Idea del algoritmo:

1.Se divide el arreglo en dos arreglos. Se repite este paso hasta que se obtienen arreglos de un solo elemento.

2.Se hace merge de los arreglos resultantes, en el orden en el que se fueron obteniendo. Este paso se repite hasta obtener el arreglo inicial pero ordenado.

Código:

Disponible en Merge Sort.

Ejemplo de uso:

Disponible en ejemplo Merge Sort.

Explicación animada:

En GeeksforGeeks: Merge Sort

Complejidad:

La complejidad del algoritmo de ordenamiento Merge Sort es O(N log N)).

Problemas en sitios jueces:

omegaUp: Merge Sorter