Skip to content

Instantly share code, notes, and snippets.

@parzibyte
Created December 18, 2021 05:07
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save parzibyte/883d44cd3f55149581279df67fb9ddb5 to your computer and use it in GitHub Desktop.
Save parzibyte/883d44cd3f55149581279df67fb9ddb5 to your computer and use it in GitHub Desktop.
"""
https://parzibyte.me/blog
"""
def merge_sort(arreglo):
longitud = len(arreglo)
mitad = longitud//2 # El doble / es para dividir y redondear hacia abajo
# Condición de salida de recursividad es que el arreglo mida 1 o 0
if longitud <= 1:
return arreglo
mitad_izquierda = arreglo[:mitad]
mitad_derecha = arreglo[mitad:]
mitad_izquierda = merge_sort(mitad_izquierda)
mitad_derecha = merge_sort(mitad_derecha)
return merge(mitad_izquierda, mitad_derecha)
def merge(izquierda, derecha):
print(f"Recibo {izquierda} y {derecha}")
arreglo_ordenado = []
indice_de_izquierda = 0
indice_de_derecha = 0
indice_arreglo_ordenado = 0
# Recorremos ambos arreglos y vamos colocando los elementos ordenados. Colocamos siempre el que sea menor
while indice_de_izquierda < len(izquierda) and indice_de_derecha < len(derecha):
valor_izquierda = izquierda[indice_de_izquierda]
valor_derecha = derecha[indice_de_derecha]
if valor_izquierda <= valor_derecha:
# El de la izquierda es menor, entonces lo ponemos primero
arreglo_ordenado.append(valor_izquierda)
# Y aumentamos en 1 el valor de la izquierda
indice_de_izquierda += 1
else:
arreglo_ordenado.append(valor_derecha)
indice_de_derecha += 1
# Sin importar lo que hayamos movido, aumentamos el índice del actual
indice_arreglo_ordenado += 1
# Hasta aquí puede que el índice izquierdo o derecho hayan llegado a su fin, pero no ambos. Entonces
# nos aseguramos de recorrerlos a ambos hasta el final
while indice_de_izquierda < len(izquierda):
arreglo_ordenado.append(izquierda[indice_de_izquierda])
indice_de_izquierda += 1
while indice_de_derecha < len(derecha):
arreglo_ordenado.append(derecha[indice_de_derecha])
indice_de_derecha += 1
print(f"Los ordeno y combino. Resultado: {arreglo_ordenado}.")
return arreglo_ordenado
arreglo = [6, 5, 3, 1, 8, 7, 2, 4]
print(f"Arreglo original: {arreglo}")
print("Ordenando con merge sort y recursividad...")
arreglo_ordenado = merge_sort(arreglo)
print(f"Arreglo ordenado: {arreglo_ordenado}")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment