Merge Sort
Merge sort es uno de los algoritmos de ordenamiento más rápidos. Muchas aplicaciones usan algunas variantes de merge sort en producción. Anteriormente hemos revisado algoritmos que funcionan en tiempo cuadrático , como Bubble sort o Selection sort. Merge sort es mucho más veloz que todos los algoritmos de ordenamiento cuadráticos y funciona en tiempo .
Merge sort es un algoritmo de divide y vencerás que ordena recursivamente partes de un arreglo y luego las combina. La base del algoritmo es su método eficiente para fusionar dos arreglos ordenados en uno solo. Durante su ejecución, merge sort divide el arreglo en dos partes. Después ordena la primera parte de forma recursiva. Luego ordena recursivamente la segunda parte. Finalmente, fusiona estas dos partes ordenadas en un nuevo arreglo:
def merge(a, b):
i, j, res = 0, 0, [] # Índice para a y b, con arreglo resultante
while i < len(a) or j < len(b): # Mientras queden elementos
ai = a[i] if i < len(a) else float('inf')
bj = b[j] if j < len(b) else float('inf')
if ai < bj: # Si a[i] < b[j], tomar a[i]
res.append(ai) # Agregar a[i] al resultado
i += 1 # Avanzar al siguiente elemento
else: # Si a[i] >= b[j], tomar b[j]
res.append(bj) # Agregar b[j] al resultado
j += 1 # Avanzar al siguiente elemento
return res
def merge_sort(a):
if len(a) <= 1: # No hay nada que ordenar
return a # Devolver arreglo inicial
l = merge_sort(a[: len(a) // 2]) # Ordenar la parte izquierda
r = merge_sort(a[len(a) // 2:]) # Ordenar la parte derecha
return merge(l, r)En cada paso, el algoritmo toma el arreglo, lo divide en dos partes, ordena cada parte por separado y fusiona los resultados en un nuevo arreglo. Observa que todos los algoritmos anteriores discutidos modificaban el arreglo in place (lo actualizaban sin crear uno nuevo), mientras que merge sort crea un nuevo arreglo en cada iteración. Lograr que merge sort funcione en modo in-place es bastante complejo. ¿Puedes explicar por qué sucede esto?
Veamos cómo funciona el algoritmo con algunos ejemplos:
[4, 1, -1, 0, 2, 8]
merge_sort([4, 1, -1, 0, 2, 8]):merge_sort([4, 1, -1])merge_sort([0, 2, 8])
merge_sort([4, 1, -1])merge_sort([4])→ return[4]merge_sort([1, -1])
merge_sort([0, 2, 8])merge_sort([1])→ return[1]merge_sort([-1])→ return[-1]
merge_sort([4, 1, -1]):
merge_sort([4])→ return[4]
merge_sort([1, -1])merge_sort([0])→ return[0]merge_sort([2, 8])
merge_sort([1, -1]):merge_sort([2])→ return[2]merge_sort([8])→ return[8]
merge_sort([1])→ return[1]
merge_sort([-1])→ return[-1]
- Vuelve a
merge_sort([1, -1])→ return[-1, 1]
Desafío
Dado un arreglo de
n enteros, se te pide ordenarlos en orden descendente usando el algoritmo Merge Sort.Entrada
La primera línea de la entrada contiene un único entero
n (1 ≤ n ≤ 100 000).La siguiente línea contiene
n enteros separados por espacio ( ≤ ≤ ) que representan el arreglo inicial.Salida
El programa debe imprimir
n enteros separados por espacio en orden descendente.Ejemplos
Entrada | Salida |
4
7 4 9 1 | 9 7 4 1 |
5
-4 8 2 -3 6 | 8 6 2 -3 -4 |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 10 MB