Ordenamiento por mezcla

Saber programar es facil, saber pensar es lo difícil.

Aumento su ki de golpe! jajaja esto se puso más serio

hice un gráfico de cómo funciona la recursividad en este algoritmo, con una lista pequeña (5,4,8,2), a mí me ayudó a entenderlo más fácil, tal vez a alguien le sirva xd

Tal vez este comentario le sirva a alguien…
Yo había olvidado que las listas en Python se pasan por referencia. Lo cual quiere decir, que si modificamos la lista dentro de la función, también lo hacemos en la lista original…

Recomiendo este video, en mi opinión explica muy bien este algoritmo. https://www.youtube.com/watch?v=XaqR3G_NVoo

Voy por las 20 veces viéndolo, espero no tener que llegar a las 100 para entenderlo.

Para los que loquieran ver de una manera mas grafica: https://visualgo.net/en/sorting

Asumí que el código haría simultáneamente el ordenamiento, tanto de la lista izquierda como el de la derecha, así como cuando al inicio de esta clase se muestra el ejemplo.

Al ver por print statements como se ejecuta el paso a paso, me quedó mucho más claro. Ahora, la idea es leer este código y comprenderlo mejor.

Dijo Freddy Vega que la mayor parte del tiempo un programador la pasa leyendo código de otros. Así que eso haré.

https://github.com/karlbehrensg/poo-y-algoritmos-python

Ordenamiento por mezcla

El ordenamiento por mezcla creado por John von Neumann el cual aplica el concepto de “divide y conquista”. Primero divide una lista en partes iguales hasta que quedan sublistas de 1 o 0 elementos. Luego las recombina en forma ordenada.

import random

def ordenamiento_por_mezcla(lista):
    if len(lista) > 1:
        medio = len(lista) // 2
        izquierda = lista[:medio]
        derecha = lista[medio:]
        print(izquierda, '*' * 5, derecha)

        # llamada recursiva en cada mitad
        ordenamiento_por_mezcla(izquierda)
        ordenamiento_por_mezcla(derecha)

        # Iteradores para recorrer las dos sublistas
        i = 0
        j = 0
        # Iterador para la lista principal
        k = 0

        while i < len(izquierda) and j < len(derecha):
            if izquierda[i] < derecha[j]:
                lista[k] = izquierda[i]
                i += 1
            else:
                lista[k] = derecha[j]
                j += 1

            k += 1

        while i < len(izquierda):
            lista[k] = izquierda[i]
            i += 1
            k +=1

        while j < len(derecha):
            lista[k] = derecha[j]
            j += 1
            k += 1
        
        print(f'izquierda {izquierda}, derecha {derecha}')
        print(lista)
        print('-' * 50)

    return lista


if __name__ == '__main__':
    tamano_de_lista = int(input('De que tamano sera la lista? '))

    lista = [random.randint(0, 100) for i in range(tamano_de_lista)]
    print(lista)
    print('-' * 20)

    lista_ordenada = ordenamiento_por_mezcla(lista)
    print(lista_ordenada)

CHICOS Si tienen problemas para entender el algoritmo les dejo este vídeo muy bueno que te explica paso a paso para que le entiendan, el código es muy parecido al de la clase

https://www.youtube.com/watch?v=FjOwTbOy18M

El código me confunde un poco en la parte de las funciones de recursión. Verán, en general, la función ordenamiento_por_lista() tiene un return. Cuando se está ejecutando y se llaman a las funciones no hay variable alguna a la cual se vaya a guardar el resultado final.

return lista

Para mi mejor entendimiento (sé que algunos le entendieron a la primera, pero en mi caso esto me ayuda) reescribí el código de la siguiente manera:

def ord_por_mezcla(lista):
    #caso base
    if len(lista) > 1:
        medio = len(lista) // 2
        izquierda = lista[:medio]
        derecha = lista[medio:]
        print(izquierda, '*' * 5, derecha)

        #llamada recursiva
        izquierda = ord_por_mezcla(izquierda)
        derecha = ord_por_mezcla(derecha)

        #iteradores para recorrer las dos sublistas
        i = 0
        j = 0
        #Iterador para la lista principal
        k = 0

        while i< len(izquierda) and j < len(derecha): #mientras podamos seguir comparando
            if izquierda[i] < derecha[j]:
                lista[k] = izquierda[i]
                i += 1
            else:
                lista[k] = derecha[j]
                j += 1
            k+= 1
        #copiar los pedazos de las listas que quedaron
        while i < len(izquierda):
            lista[k] = izquierda[i]
            i+=1
            k += 1
        while j < len(derecha):
            lista[k] = derecha[j]
            j += 1
            k += 1
        print(f'izquierda  {izquierda}. derecha  {derecha}')
        print(lista)
        print('--' * 30)

    return lista

Heme aqui, casi a las 2AM leyendo y releyendo mi codigo el cual ya entendi como funciona, lo redacte y copie igual a como muchos lo tienen aqui…y mi cerebro esta colapsano un poco que nomas no lo organiza, y ahora cada que lo imprimo literal me modifica los valores. Aplicare la vieja y confiable, me voy a dormir un rato y regreso a darle otra checada, ya que este fresque como lechuge.

Hola! Este código no es mio, pero pensé en compartirlo porque se trata de un algoritmo muy similar pero implementado de una forma muy elegante, se está haciendo básicamente lo mismo, pero con menos líneas de código:

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)
    
print (quicksort([35,8,58,68,65,42,93,86,2,1,90]))
# Prints "[1, 2, 8, 35, 42, 58, 65, 68, 86, 90, 93]"

PD Lo modifiqué un poco para que fuera compatible con Python 3.

https://github.com/tuanavu/Stanford-CS231/blob/master/notes/0-preparation/python-numpy-tutorial.md

Les dejo este pequeño diagrama con un ejemplo de como funcional el algoritmo, le faltan por especificar varios detalles pero pensé que a alguno le podría servir para entender.

No lo entendí y le dedique bastante tiempo. La verdad pienso que esta muy mal explicado.

este es el tema mas complejo que he visto hasta ahora. solo me da animo escuchar lo que el profe dice, que no importa si lo tengo que leer hasta 10.000 veces con tal que lo entienda

Hola, aquí dejo un enlace con la visualización de distintos algoritmos de ordenamiento, que les puede ser muy útil para entenderlos. Puede ayudar a entender la pila de recursividad del merge sort.
https://www.hackerearth.com/practice/algorithms/sorting/merge-sort/visualize/

Es normal que esta clase se haga un poco difícil, a mi me ayudo mucho volver a ver la clase de recursividad del curso pasado
https://platzi.com/clases/1764-python-cs/25243-recursividad/

La verdad es que estuve literalmente una hora viendo el codigo para entenderlo al 100%, me habia olvidado de como funcionaba el almacenamiento de listas, pero al final pude agarrarle la mano jajaja todo es cuestion de paciencia

Para mi el código se divide en estas secciones:

1.- Divide las listas hasta el minimo
2.- Compara los elementos y ordena
3.- (La seccion de los 2 while) Pone el ultimo elemento ya sea de izquierda o derecha

Creo que como todos la manera de entender es que pensabamos que el computador iba a hacer todo como nosotros lo hacemos en la cabeza y era que lo iba a hacer simultaneamente derecha e izquierda, pero viendo como funciona es lo maximo. Es una explosion mental

Les dejo una imagen que me ayudo a entender un poco mejor el codigo.

Y bueno, la primer imagen que aparece si buscas merge sort, pero igual me ayudo. xd

Chicos, por fa me pueden ayudar con una inquietud.

Cuando hace las llamadas de recursividad, esta ordenando las listas izquierda y derecha ¿verdad?

Por lo tanto me surge una pregunta. ¿Por qué NO se escribe el codigo de recursividad de la siguiente manera?:

izquierda = ordenamiento_por_mezcla(izquierda)
derecha = ordenamiento_por_mezcla(derecha)

Acaso ¿esto sucede porque la lista (izquierda o derecha) utiliza el mismo espacio en memoria? o ¿por que?

El big O de los diferentes algoritmos de ordenamiento tanto en tiempo como en memoria

hice mi version de lo que entendi y queria saber si el pop hace que gaste mas recursos

from random import randint 

def por_mescla(lista):
    
    n = len(lista)

    if n <=1:
        return lista
    else:
        medio = n //2
        l1 = por_mescla(lista[:medio])
        l2 = por_mescla(lista[medio:])

        lista_final = []
        print(f'llega {lista}')
        print(f'{lista[:medio]} se convierte en {l1}')
        print(f'{lista[medio:]} se convierte en {l2}')
        print(n)

        for i in range(n):
            if len(l1) == 0:
                lista_final += l2
                break

            elif len(l2) == 0:
                lista_final += l1
                break

            elif l1[0] <= l2[0]:
                lista_final.append(l1[0])
                l1.pop(0)

            elif l1[0] > l2[0]:
                lista_final.append(l2[0])
                l2.pop(0)

        print(f'final{lista_final}')
        print('-'*50)
        return lista_final

aqui veran como funciona este algoritmo con un poco de baile

Un video didactico sobre los merge sort y quick sort

Esta muy bueno este código es “hermoso”.

algoritmos de ordenación

https://gist.github.com/andaviaco/10949335

Al comparar los tres algoritmos de ordenamiento que vimos en el curso, si es concluyente que el de mezcla es mas rápido.
Dejo el link de el código que utilicé GitHub

PDTA: Si está bien complicado el de mezcla haha vi el video varias veces !

Entiendo la recursividad pero lo que me falta por comprender son las variables i,j,k hahaha xd, a leer el codigo mil veces voy😅

entiendo el concepto pero no el codigo

Estábamos programando tranquilos y de repente me sueltan esto. No me haga esto oiga´.

No tienen un curso de cómo desbloquear tu cerebro después de estas clases?

Me resulto difícil entender el código y principalmente fue por la recursividad. Para entenderlo, tuve que recurrir a realizar un esquema del funcionamiento del código. A continuación lo publico, es probable que otra persona le suceda lo mismo.

He notado que somos unos cuantos a los que nos ocurre que comprendemos la lógica detrás de los algoritmos, pero su implementación a código usando los ejemplos del profesor nos cuesta trabajo.
Una recomendación personal que puedo hacer a cualquiera que este siguiendo el curso y le cueste, como a mí, entender los códigos. Es quedarse con la explicación conceptual del profesor, interiorizarla y después complementar con tutoriales en internet de la implementación del código.
Básicamente por que el fuerte del profesor David, es transmitir el razonamiento detrás de los algoritmos, pero decae un poquito en cuanto a que tan legible es el código para gente que recién comienza en la programación.
Y en la gran mayoría de los tutoriales de internet, los códigos son mucho más explícitos, y amigables para su lectura e interpretación, pero casi nunca profundizan en la parte lógica tras los algoritmos.
Personalmente me esta ayudando mucho a no atascarme.
Aquí un ejemplo del video que utilicé para entender el código de merge_sort.
https://www.youtube.com/watch?v=Lk5Ql4_VeUs

soy el unico que entiende el algortimo, pero no entiende por que el codigo mostrado funciona?

En este momento, me pareció bien un repaso por el código de Recursividad básico (con factorial) #volver a las bases.
Capaz a alguien le sirva:

# definición de factorial expresado de tres maneras (pseudocódigo) para tener a  mano antes de empezar el código

factorial =  n * factorial de n-1 
factorial = n * (n-1)! 
factorial =  n * factorial(n-1)


#comienza el código:

def factorial(n):

    print("Entra a la función factorial, n vale: ", n)

    if (n > 1):
    
        #Si n es mayor a 1, entonces se vuelve a llamar la función que multiplica a n * (n -1)

        print("Como es mayor a 1, la función se llamara a si misma otra vez.\n")

        return n * factorial(n-1) # aquí se está llamando a sí misma
    
    else:
    
        #Si n es igual 1, ya no se llama la funció a sí misma y terminará la recursividad.

        print("n es igual a 1, termina la recursividad.\n")
        return 1
    


if __name__ == '__main__':

    print("\nRecursividad - Factorial\n\n")

    res = factorial(5)
    print("\nEl resultado es:  \n\n", res)

    

Hice una comparación de todos los algoritmos que vimos según la cantidad de elementos del arreglo y el tiempo (en segundos) que tardan. Esto usando el método de tomar el tiempo ante y después de aplicar el algoritmo y después sacar la diferencia.
(Los que están con signos de pregunta tardaban demasiado tiempo o se me trabo la computadora en medio de la espera)

• Búsqueda Lineal: T(n) = O(n)
  Elementos Tiempo
  1.000 -> 0,0
  10.000 -> 0,001
  100.000 -> 0,005
  1.000.000 -> 0,032
  10.000.000 -> 0,306
  100.000.000 -> 3,894
  1.000.000.000 -> ???

• Busqueda Binaria: T(n) = o(log n)
  Elementos Tiempo
  1.000 -> 0,0
  10.000 -> 0,0009
  100.000 -> 0,003
  1.000.000 -> 0,032
  10.000.000 -> 0,317
  100.000.000 -> 3,249
  1.000.000.000 -> ???

• Bubble Sort: T(n) = O(n^2)
  Elementos Tiempo
  100 -> 0.002
  1.000 -> 0,093
  10.000 -> 10,65
  100.000 -> 1031.36
  1.000.000 -> ???

• Insert Sort: T(n) = O(n^2)
  Elementos Tiempo
  100 -> 0.0
  1.000 -> 0,055
  10.000 -> 5,53
  100.000 -> 586.36
  1.000.000 -> ???

• Merge Sort: T(n) = O(n log n)
  Elementos Tiempo
  100 -> 0.0
  1.000 -> 0,003
  10.000 -> 0,058
  100.000 -> 0,663
  1.000.000 -> 7,809
  10.000.000 -> 91,093
  100.000.000 -> ???

a mi se me hace mas intuitivo asi:

def merge_sort(lista):
    
    if len(lista) <= 1:
        return lista

    middle = len(lista) // 2

    left = merge_sort(lista[:middle])
    right = merge_sort(lista[middle:])

    temp_list = []

    while len(left) > 0 and len(right) > 0:

        if right[0] < left[0]:
            temp_list.append(right[0])
            del right[0]
        else:
            temp_list.append(left[0])
            del left[0]
    
    temp_list.extend(left)
    temp_list.extend(right)

    return temp_list

Quiero hacer un aporte ya sea que creo que es un poco básico, pero ahí les va para alguien que tenga la misma duda que yo:
Yo llegaba a entenderlo conceptualmente pero tenía una duda en el código especificamente en esta parte cuando se llamaba recursivamente:

ordenamiento_por_mezcla(izquierda)
ordenamiento_por_mezcla(derecha)

como solo se llamaba y no almacenaba en ninguna variable para no perder los datos como era mi lógica, ejemplo:

# Observación: asi tambien funciona :)
izquierda = ordenamiento_por_mezcla(izquierda)
derecha = ordenamiento_por_mezcla(derecha)

yo creía que los valores se perdian al no ser guardados y supuestamente no tendría que ordenarse, pero luego recordé la clase de scope(alcance de variables) me di cuenta que lo que se modificaba en cada llamada correspondia a cada variable sin necesidad de explicitamente asignarla. En esta parte todo lo que se modifique dentro de la función afectará a cada variable ya que tienen el mismo id, puedes corroborarlo a través de los print statement :

# Así es como me di cuenta :)
print(id(merge_sort(left)), id(left), id(right))
print(id(merge_sort(right)), id(left), id(right))

con esto logré resolver la duda que tenía, espero les sirva de ayuda y si me equivoque en algo por favor que lo explique en los comentarios para que todos podamos entender.

Creo que me complique un poco … 👀

def merge_sort(lista):
    if len(lista) > 1:
        mitad = len(lista)//2
        aux_list=[]
        listas = [merge_sort(lista[:mitad]),merge_sort(lista[mitad:])]
        size_lists= [len(listas[0]),len(listas[1])] 
        flag = 0 if size_lists[0] > size_lists[1] else 1
        max_list = listas[flag]
        min_list = listas[abs(flag-1)]
        count_maxlist, count_minlist = 0, 0
        for i in range(len(max_list)):
            if count_minlist <= len(min_list)-1:
                for j in range(count_minlist,len(min_list)):
                    if max_list[i] <= min_list[j]:
                        aux_list.append(max_list[i])
                        count_maxlist +=1
                        break
                    else:
                        aux_list.append(min_list[j])
                        count_minlist +=1
            else:
                break

        while count_maxlist <= len(max_list) -1:
            aux_list.append(max_list[count_maxlist])
            count_maxlist += 1

        while count_minlist <= len(min_list) -1:
            aux_list.append(min_list[count_minlist])
            count_minlist += 1
        
        return aux_list
    else:
        return lista

Les recomiendo que coloquen un

breakpoint()

al inicio de la función de ordenamiento por mezcla, eso les ayudara para saber que pasa en cada línea de código.

Una forma de verlo graficamente, la parte azul es la recursividad y la parte naranja donde se van ordenando las listas

Aporte

Tuve que borrar y escribir el algoritmo como 5 veces para entenderlo, al final lo lo logré… les comparto mi código con anotaciones.

Código

import random

def merge_sort(dataset):
    """Sorts a list of numbers using the Merge Sort algorithm.

    The original list will be mutated.

    Time Complexity: O(n log n)
    """
    dataset_len = len(dataset)

    # Se verifica si la lista proporcionada tiene más de un elemento,
    # esto será la condición que pare la recursión dado que estamos basando
    # nuestra lógica en el principio de que una lista de 1 elemento es igual
    # a una lista ordenada.
    if dataset_len > 1:
        middle = dataset_len // 2
        # Ordenamos el lado izquiedo de la lista
        left = merge_sort(dataset[0:middle])
        
        # Ordenamos el lado derecho de la lista
        right = merge_sort(dataset[middle:])

        # Obtenemos el número de elementos en cada sub lista.
        # Solo lo guardamos en una variable por que se utiliza repetidamente
        # en las siguentes líneas.
        left_len = len(left)
        right_len = len(right)

        # Sub nodes iterators

        # Definimos unas banderas de iteración que nos ayudarán a recorrer los índices de cada sub-lista (Izquierda y derecha)
        left_idx = 0
        right_idx = 0
        
        # Iterator of the main list

        # Definimos una bandera de iteración que nos ayudará a recorrer nuestra lista principal
        index = 0


        # Este ciclo lo que hará es unir (Merge) las dos listas generadas, con la condición
        # de que los índices no sobre pasen el número de elementos de su lista respectiva.
        # 
        # Esto significa que puede llegar el caso en el que la longitud de las 2 listas sea diferente
        # y una de las 2 listas se termine de unir a la lista principal primero. 
        while left_idx < left_len and right_idx < right_len:
            
            # Revisamos en qué lista está el valor más pequeño y lo unimos a la lista principal
            if left[left_idx] < right[right_idx]:

                # Si el valor más pequeño estaba en la lista izquierda lo añadimos a la lista principal
                # e incrementamos el índice izquierdo para no re-evaluar el mismo valor en la iteración siguiente.
                dataset[index] = left[left_idx]
                left_idx += 1
            else:
                # Si el valor más pequeño estaba en la lista derecha lo añadimos a la lista principal
                # e incrementamos el índice derecho para no re-evaluar el mismo valor en la iteración siguiente.
                dataset[index] = right[right_idx]
                right_idx += 1
            
            # Incrementamos el índice de la lista principal indicando que el valor colocado en esa posición
            # ya está ordenado.
            index += 1

        # Una vez llegado a este paso nuestra lista principal ya está casi completamente ordenada,
        # pero como comentamos anteriormente, es posible que una de las 2 listas sea más grande
        # que la otra, por lo pueden existir números de una de las 2 listas que no hayamos unido a 
        # la lista principal.
        # 
        # Es importante tener en cuenta que aunque a continuación se recorren las 2 listas, es imposible
        # que se ejecuten los 2 ciclos, dado que solo puede haber sobrado números en una de las 2 sub-listas
        # y la razón de que estén los 2 ciclos (uno para cada sub-lista) es que no sabes a cuál le sobraron
        # números y dado el comportamiento del ciclo while solo se ejecutará aquél ciclo cuya lista tenga
        # sobrantes y se añadirán al final de la lista principal.
        while left_idx < left_len:
            dataset[index] = left[left_idx]
            left_idx += 1
            index += 1
        
        while right_idx < right_len:
            dataset[index] = right[right_idx]
            right_idx += 1
            index += 1

    return dataset


if __name__ == '__main__':
    list_size = int(input('¿De qué tamaño será la lista?'))

    dataset = [random.randint(0, 100) for i in range(0, list_size)]

    print('Unsorted list', dataset)
    merge_sort(dataset)
    print('=' * 15)
    print('Sorted list', dataset)

No comprendí joder c:

Comunidad, he agregado varios print statements para que se vea qué ejecuta el sistema paso a paso y así poder entender bien el ordenamiento por mezcla. Espero les sirva y si ven alguna mejora que se pueda hacer, me avisan.

import random

def ordenamiento_por_mezcla(lista):
if len(lista) > 1:
medio = len(lista) // 2 #divido entre 2 el tamaño de la lista. Con esto podré indicar los límites de 2 sublistas
izquierda = lista[:medio] #divido la lista desde el inicio hasta el valor del medio
derecha = lista[medio:] # y desde el valor del medio hasta el final
print(izquierda, “*” * 5, derecha) # imprimo las 2 sub listas

    #realizo la recursividad de tal forma que cada vez se vayan dividiendo
    #las listas entre 2 hasta que cada valor quede de forma independiente
    #esto lo realizo para las sublista de la izquierda y derecha
    ordenamiento_por_mezcla(izquierda)
    ordenamiento_por_mezcla(derecha)

    #Tengo que recorrer las listas para comparar los valores y ordenar
    #para esto creo 2 iteradores
    i = 0
    j = 0
    #asimismo, creo un tercer iterador para recorrer la lista principal
    #en donde se alojarán los valores ordenados poco a poco
    k = 0
    
    while i < len(izquierda) and j < len(derecha):
        #si el primer valor de la sublista izquierda es menor que el 
        #primer valor de la sublista derecha, entonces
        print(i, "<", len(izquierda), " y ", j, "<", len(derecha), "?")
        if izquierda[i] < derecha[j]:
            print("Sí, entonces :", izquierda[i], "<", derecha[j], "?")
            #la lista en la primera posición, tomará el valor de izquierda
            lista[k] = izquierda[i]
            print("si,", izquierda[i], "se agrega a la lista")
            #le sumo 1 para ir a la siguiente posición dentro de la sublista izquierda
            i += 1
            print("incrementamos en 1 el valor de i")
        else:
            print(izquierda[i], "<", derecha[j], "?")
            #caso contrario, la lista en su primera posición
            #asumirá el valor de la sublista derecha en su primera posición
            lista[k] = derecha[j]
            print("No, entonces ", derecha[j], "se agrega a la lista")
            j += 1
            print("incrementamos en 1 el valor de j")
        print("incrementamos en 1 el valor de k")
        k += 1
        print("i=", i, "j=", j, "k=", k)
    while i < len(izquierda):
        print(i, "<", len(izquierda))
        lista[k] = izquierda[i]
        print(izquierda[i], "se agrega a la lista")
        i += 1
        k += 1
    
    while j < len(derecha):
        print(j, "<", len(derecha))
        print(derecha[j], "se agrega a la lista")
        lista[k] = derecha[j]
        j += 1
        k += 1
    
    print(f"izquierda {izquierda}, derecha {derecha}")
    print("la lista queda de la siguiente forma: ", lista)
    print("-" * 50)

    return lista

if name == “main”:
#defino el tamaño de la lista
tamano_lista = int(input(“Ingrese el tamaño de la lista: “))
#asigno valores aleatorios de acuerdo al tamaño de la lista ingresado
lista = [random.randint(0, 100) for i in range(tamano_lista)]
#imprimo los valores de la lista
print(lista)
print(”*” * 50)

#llamo a una función que ordene la lista.
#En este caso, el ordenamiento se realizara con el metodo de mezcla
#le doy como parametro la lista previamente creada con valores aleatorios
lista_ordenada = ordenamiento_por_mezcla(lista)
#imprimo la lista ordenada
print(lista_ordenada)

Tuve un problema con el código del profesor respecto a las variables izquierda y derecha que se declaran dentro del if, me tiraba el error “UnboundLocalError: local variable ‘izquierda’ referenced before assignment”, las saqué del if y las puse antes, de modo que su alcance sea en toda la función, y ahí si anduvo todo perfecto.

Algoritmo de ordenamiento rápido o quicksort:

Les dejo esta implementación hecha en Python, fue bastante complejo entender como funciona y justamente donde realizar el llamado de la recursividad pero vale la pena.

import random

def ordenamiento_rapido(lista, izq, der):

    if izq < der:
        pivote = lista[izq] #Inicialmente toma el valor de la posición 0, a medida q se va aplicando la recursividad
                            #obtiene un nuevo valor pivote de acuerdo a la posición.
        i = izq             #Inicialización de indices i y j para luego recorrer la lista de der a izq y de izq a der
        j = der        
        while ( i < j ):
            while ( lista[i] < pivote ): #Mientras el valor que tiene en esa posición i es menor q pivote incrementa su valor, es decir no debe realizar
                                         #intercambio
                i+=1
            while lista[j] > pivote:     #Mientras el valor que tiene en esa posición j es mayor que pivote incrementa su valor, es decir no debe realizar
                                         #intercambio
                j-=1
            if i < j:                   
                temp = lista[i]          #se declara un objeto temporal para hacer el intercambio de posiciones
                lista[i] = lista[j]
                lista[j] = temp

        ordenamiento_rapido(lista, izq, j-1) #Llamado recursivo lista menor que pivote, posicion inicial hasta la posición del pivote - 1
        ordenamiento_rapido(lista, i+1, der) #Llamado recursivo lista mayor que pivote, posicion pivote + 1 hasta el final de la lista

    return lista

if __name__ == '__main__':
    tamano_de_lista = int(input('De que tamano sera la lista? '))

    lista = [random.randint(0, 100) for i in range(tamano_de_lista)]
#    lista = [8, 4, 9, 3, 5, 7, 1, 6, 2]
    print(f'Lista inicial en desorden: {lista}')

    lista_ordenada = ordenamiento_rapido(lista, 0, len(lista)-1)
    print(f'Lista en orden: {lista_ordenada}')

después de un buen rato le entendí

import random


def ordenamiento_por_mezcla(lista):
    if len(lista) > 1: #Longitud de la lsita es mayor a 1 ---> Ya hicios la lista suficientemente pequeña
        #no ejecuta nada porque significa que ya esta completo
        medio = len(lista) // 2 #primero debemos encontrar la mitad

        izquierda = lista[:medio] # lista de 0 hasta la mitad
        derecha = lista[medio:] # lista de la mitad hasta el final ### NOTACION DE REBANADA
        print(izquierda, "*" * 5, derecha)
        #Llamada recursiva en cada mitad
        ordenamiento_por_mezcla(izquierda)
        ordenamiento_por_mezcla(derecha)
        #Crecimiento logaritmico

        #Crear 2 iteradores para recorrer las 2 sublistas
        i = 0
        j = 0
        k = 0 #Sirve para iterar en la lista principal

        #comparaciones 
        while i < len(izquierda) and j < len(derecha): #Si se cumplen estas 2 condiciones podremos seguir comparando
            if izquierda[i] < derecha[j]:
                lista[k] = izquierda[i]
                i += 1
            else:
                lista[k] = derecha[j]
                j += 1
            
            k += 1
        
        while i < len(izquierda):
            lista[k] = izquierda[i]
            i += 1
            k += 1
        
        while j < len(derecha):
            lista[k] = derecha[j]
            j += 1
            k += 1
        
        print(f"Izquierda: {izquierda}, Derecha: {derecha}")
        print(lista)
        print(i)
        print(j)
        print(k)
        print("_" * 5)
        
    return lista


if __name__ == "__main__":
    tamano_de_lista = int(input("¿Que cantidad de datos tendra la lista?: "))

    lista = [random.randint(0, 100) for i in range(tamano_de_lista)]
    print(lista)
    print("_" * 40)

    lista_organizada = ordenamiento_por_mezcla(lista)
    print(lista_organizada)

ganan en tiempo, pero pierde en memoria

No lo voy a negar me costo un poco repetí el vídeo como 20 veces pero me quedo claro lo que me quedo un poco en el aire es los 2 últimos wile se que es para que copien los elementos que faltan pero el j += 1 y el i +=1 no entiendo como detienen el loop pero me gusto la menara en que funciona el ordenamiento por mezcla dividiendo la lista hasta que quede 1 elemento y luego rearmando la ordenada.

Este me costó, pensé que estaba entendiendo recursividad pero pregunto: Los ciclos while no se ejecutan sino hasta que solo se tenga lista de 1 elementos?

Me costó entenderlo, pero si vas revisando paso a paso, te vas dando cuenta como va siendo el proceso.

https://runestone.academy/runestone/static/pythoned/SortSearch/ElOrdenamientoPorMezcla.html

Que código tan interesante, me gusto mucho la clase

MergeSort siempre tiene O(n log n) de tiempo, pero puede mejorarse el espacio utilizado. En la implementación que se muestra en la clase estamos usando O(n log n) de espacio en memoria.

Aquí les dejo otra implementación que solo crece O(n) de espacio, pues solamente crea un array auxiliar en vez de dividir el original. Además hace la mutación in situ.
Ojalá les guste:

def mergeSort(array):
    if len(array) <= 1:
		return array
	auxiliaryArray = array[:]
	mergeSortHelper(array, 0, len(array) - 1, auxiliaryArray)
	return array
		
def mergeSortHelper(mainArray, startIdx, endIdx, auxiliaryArray):
	if startIdx == endIdx:
		return
	middleIdx = (startIdx + endIdx) // 2
	mergeSortHelper(auxiliaryArray, startIdx, middleIdx, mainArray)
	mergeSortHelper(auxiliaryArray, middleIdx + 1, endIdx, mainArray)
	doMerge(mainArray, startIdx, middleIdx, endIdx, auxiliaryArray)
	
def doMerge(mainArray, startIdx, middleIdx, endIdx, auxiliaryArray):
	k = startIdx
	i = startIdx
	j = middleIdx + 1
	while i <= middleIdx and j <= endIdx:
		if auxiliaryArray[i] <= auxiliaryArray[j]:
			mainArray[k] = auxiliaryArray[i]
			i += 1
		else:
			mainArray[k] = auxiliaryArray[j]
			j += 1
		k += 1
		
	while i <= middleIdx:
		mainArray[k] = auxiliaryArray[i]
		i += 1
		k += 1
		
	while j <= endIdx:
		mainArray[k] = auxiliaryArray[j]
		j += 1
		k += 1

Me encanta la cara de David cuando empieza a explicar el algoritmo, su sonrisa y emoción me recordó a mí haciendo mi trabajo, disfruta hablando de estos temas y también inspira a seguir aprendiendo.

alguien me explica bien la funcion del primer while que usamos

No entiendo cuando se deja de ejecutar la recursividad!

def ordenamiento_por_mezcla(lista):
  if len(lista) > 1:
    medio = len(lista) // 2
    izquierda = lista[:medio]
    derecha = lista[medio:]
    print(f'dividiendo izquierda: {izquierda} derecha {derecha}')

    # llamada recursiva en cada mitad
    ordenamiento_por_mezcla(izquierda)
    ordenamiento_por_mezcla(derecha)
    print('y esto pa cuando')

    # Iteradores para recorrer las dos sublistas
    i = 0
    j = 0
    # Iterador para la lista principal
    k = 0```
El código me funciona, pero no logro entender porqué se deja de ejecutar la recursividad y empieza a comparar! 

Para el que aún no entendió, como yo hace 2 días, les dejo el código con los print statements en cada paso para que vena qué es lo que hace el sistema. Espero sea de ayuda. Un abrazo

import random

def ordenamiento_por_mezcla(lista):
if len(lista) > 1:
medio = len(lista) // 2 #divido entre 2 el tamaño de la lista. Con esto podré indicar los límites de 2 sublistas
izquierda = lista[:medio] #divido la lista desde el inicio hasta el valor del medio
derecha = lista[medio:] # y desde el valor del medio hasta el final
print(izquierda, “*” * 5, derecha) # imprimo las 2 sub listas

    #realizo la recursividad de tal forma que cada vez se vayan dividiendo
    #las listas entre 2 hasta que cada valor quede de forma independiente
    #esto lo realizo para las sublista de la izquierda y derecha
    ordenamiento_por_mezcla(izquierda)
    ordenamiento_por_mezcla(derecha)

    #Tengo que recorrer las listas para comparar los valores y ordenar
    #para esto creo 2 iteradores
    i = 0
    j = 0
    #asimismo, creo un tercer iterador para recorrer la lista principal
    #en donde se alojarán los valores ordenados poco a poco
    k = 0
    
    while i < len(izquierda) and j < len(derecha):
        #si el primer valor de la sublista izquierda es menor que el 
        #primer valor de la sublista derecha, entonces
        print(i, "<", len(izquierda), " y ", j, "<", len(derecha), "?")
        if izquierda[i] < derecha[j]:
            print("Sí, entonces :", izquierda[i], "<", derecha[j], "?")
            #la lista en la primera posición, tomará el valor de izquierda
            lista[k] = izquierda[i]
            print("si,", izquierda[i], "se agrega a la lista")
            #le sumo 1 para ir a la siguiente posición dentro de la sublista izquierda
            i += 1
            print("incrementamos en 1 el valor de i")
        else:
            print(izquierda[i], "<", derecha[j], "?")
            #caso contrario, la lista en su primera posición
            #asumirá el valor de la sublista derecha en su primera posición
            lista[k] = derecha[j]
            print("No, entonces ", derecha[j], "se agrega a la lista")
            j += 1
            print("incrementamos en 1 el valor de j")
        print("incrementamos en 1 el valor de k")
        k += 1
        print("i=", i, "j=", j, "k=", k)
    while i < len(izquierda):
        print(i, "<", len(izquierda))
        lista[k] = izquierda[i]
        print(izquierda[i], "se agrega a la lista")
        i += 1
        k += 1
    
    while j < len(derecha):
        print(j, "<", len(derecha))
        print(derecha[j], "se agrega a la lista")
        lista[k] = derecha[j]
        j += 1
        k += 1
    
    print(f"izquierda {izquierda}, derecha {derecha}")
    print("la lista queda de la siguiente forma: ", lista)
    print("-" * 50)

    return lista

if name == “main”:
#defino el tamaño de la lista
tamano_lista = int(input("Ingrese el tamaño de la lista: "))
#asigno valores aleatorios de acuerdo al tamaño de la lista ingresado
lista = [random.randint(0, 100) for i in range(tamano_lista)]

#imprimo los valores de la lista
print(lista)
print("*" * 50)

#llamo a una función que ordene la lista.
#En este caso, el ordenamiento se realizara con el metodo de mezcla
#le doy como parametro la lista previamente creada con valores aleatorios
lista_ordenada = ordenamiento_por_mezcla(lista)
#imprimo la lista ordenada
print(lista_ordenada)

Este video me ayudo mucho a ver gráficamente como funciona la recursividad en el ejercicio. https://www.youtube.com/watch?v=nga05GPMsRs

Concuerdo que este algoritmo tiene una complejidad logarítmica. Ejecuté pruebas utilizando un Jupyter Notebook corriendo en Docker con 1 CPU.

10 Elementos (116 micro-segundos por loop)

3.1 ms ± 116 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

100 Elementos (530 micro-segundos por loop)

16.7 ms ± 530 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

1000 Elementos (3.74 mili-segundos por loop)

165 ms ± 3.74 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

Si a alguien le está costando como a mi entender bien el código le recomiendo lo siguiente (porque después de 1 hora literalmente leyendo y releyendo entendí jaja)

• PRIMERO: Mira TODO el video de recorrido (aún si no entiendes la mayoría)
• SEGUNDO: NO te fijes en la teoría que se muestra al principio de la clase, fíjate mejor en lo que imprime el programa en el minuto 15:34 ya que ahí la teoría lo ves de mejor manera
• TERCERO: Entiende la primera parte del código que dividide la lista desordenada en listas “ordenada” de un solo elemento
• CUARTO: Copia a mano en un papel separado lo que está en el minuto 15:34 y luego pon en la pantalla el código para que a medida que vayas leyendo el código vayas viendo lo que imprime
• QUINTO: cae en cuenta que lo MÁS IMPORTANTE DE AQUÍ (por lo menos para mi cuando lo empecé a entender) Es el CONTEXTO DE EJECUCIÓN. si se dan cuenta, la primera ves que se imprime, todo ocurre literalmente en la línea de código que dice “ordenamiento_por_mezcla(izquierda)” (piensen)
• SEXTO: repasen el primer paso a lo largo del código y haganlo manualmente diciendo que pasa en cada una de las líneas.

Por lo menos así me sirvió a a mi =)

Claro como el chocolate espeso… la verdad es que si se entiende luego de hacer los prints y ver el video explicativo del compañero

Esto sería como una propiedad asociativa, pero en vez de multiplicar comparo con mayor que. Se me erizó la piel de ver como funcionaba

Explicación gráfica de los pasos:

Hola! Con este diagrama y dejando explícito por donde va el código me ayudo muchísimo. Dejo ambos. Saludos!

import random

def ordenamiento_por_mezcla(lista):
    if len(lista) > 1:
        medio = len(lista) // 2
        izquierda = lista[:medio]
        derecha = lista[medio:]
        print(izquierda, '*' * 5, derecha)

        # llamada recursiva en cada mitad
        print('empieza ordenamiento por mezcla izquierda')
        ordenamiento_por_mezcla(izquierda)
        print('termina ordenamiento por mezcla izquierda')
        print('empieza ordenamiento por mezcla derecha')
        ordenamiento_por_mezcla(derecha)
        print('termina ordenamiento por mezcla derecha')

        # Iteradores para recorrer las dos sublistas
        i = 0
        j = 0
        # Iterador para la lista principal
        k = 0

        while i < len(izquierda) and j < len(derecha):
            print(f'lista en primer ciclo while {lista}')
            print('entra a primer ciclo while')
            if izquierda[i] < derecha[j]:
                print('entra a if parte de primer ciclo while')
                lista[k] = izquierda[i]
                i += 1
                print(f'i={i}')
                print(f'lista k if en primer ciclo while: {lista}')
            else:
                print('entra a else de primer ciclo while')
                lista[k] = derecha[j]
                j += 1
                print(f'j={j}')
                print(f'lista k else de ciclo while: {lista}')

            k += 1
            print(f'k={k}')
            print(f'lista después de salir de primer ciclo while={lista}')
        while i < len(izquierda):
            print('segundo ciclo while')
            lista[k] = izquierda[i]
            i += 1
            k +=1
            print(f'i={i}')
            print(f'k={k}')
            print(f'lista k en segundo ciclo while: {lista}')

        while j < len(derecha):
            print('tercer ciclo while')
            lista[k] = derecha[j]
            j += 1
            k += 1
            print(f'j={j}')
            print(f'k={k}')
            print(f'lista k en tercer ciclo while: {lista}')
        
        print(f'izquierda {izquierda}, derecha {derecha}')
        print(lista)
        print('-' * 50)
    print('termina ciclo de if')
    return lista
print('termina funcion')

if __name__ == '__main__':
    tamano_de_lista = int(input('De que tamano sera la lista? '))

    lista = [random.randint(0, 100) for i in range(tamano_de_lista)]
    print(lista)
    print('-' * 50)

    lista_ordenada = ordenamiento_por_mezcla(lista)
    print('termino')
    print(lista_ordenada)

Que buena clase!.

Esta clase me rompió la cabeza jajaj. Muy buena!

Aquí encontré otra definición y código fácil de comprender, espero le sirva. En este video también hay un ejercicio para que repasen el código.

wow! No lo entendí jajajaja a buscar info :3

Hola equipo, me sirvió mucho hacerle debug al código, que explica Facundo en el siguiente video:
https://platzi.com/clases/2255-python-intermedio/36469-debugging/

Me duele la cabeza pero por fin lo entendí:
Les comparto los puntos claves que yo considero me ayudaron a comprenderlo.
Cuando realiza las llamadas recursivas por cada mitad estas funciones modifican las sublistas por lo que en teoría retornan el contenido de cada mitad ordenado, es decir, que cuando empiezan los ciclos estos reciben dos listas previamente ordenadas, empezando por el ultimo nivel donde las listas solo tienen un solo elemento, por otro lado, si se fijan en el primer ciclo while, en cada iteración solo uno de los iteradores de las sublistas se incrementa, por eso es necesario los otros whiles, que agregan lo que ya no se puede comparar pero que ya esta organizado.

Queriendo comprender como funciona este algoritmo, utilice la herramienta de VSC de Debbuging y puse breakpoints en todas las lineas del cuerpo de la función recursiva ordenamiento_por_mezcla() para ver como las variables locales (lista, medio, izquierda y derecha) iban modificando su valor en cada recursion, Me llamo mucho la atención que estas variables locales (recuerdan) el valor de la recursion anterior, Asi que busque en internet como se comportan las variable locales en funciones repulsivas y me encontré esto:

El orden inverso de ejecución es una característica típica de todas las funciones recursivas. Si una función recursiva tiene variables locales, se creará un conjunto diferente de variables locales durante cada nueva llamada. Los nombres de las variables locales serán los mismos, como los hallamos declarado en la función. Sin embargo, las variables representarán un conjunto diferente de valores cada vez que se ejecute la función. Cada conjunto de valores se almacenará en la pila, así cuando el proceso recursivo se deshaga (cuando las llamadas a la función se saquen de la pila y sigan su ejecución) podremos disponer de ellas.

https://ccia.ugr.es/~jfv/ed1/c/cdrom/cap6/cap66.htm

Lo comparto por acá por si le ayuda a alguien mas a comprender la recursividad, a mi me pareció super interesante.

Qué algoritmo tan brutal! Me ordenó 1 MILLÓN de números en tan solo 20 segundos! 🥶

Algo que me ayudó a entender el código fue, que en python, los parámetros son referencia.

📢Pequeños aportes que (quizá) te ahorraran tiempo :

1. Recuerda que las listas al ser modificadas en una función son modificadas en su instancia original

2. Usa el debugger de VScode y presta atención a las variables izquierda y derecha, además del desarrollo del ordenamiento

3. Si sabes ingles este video te aclarará muchas dudas.

4. Este video en español también puede ayudarte

5. La parte de los iteradores yo lo entendí como:
   - Ya analizamos este elemento ( i = 0 \ j =0 ) pasemos al siguiente( i +=1 \ j += 1)
   - Estoy ordenando este elemento ( k = 0 ) ahora ordenamos este ( k += 1 )

6. Nota mental : Repasa mañana que probablemente se te olvide lo poco que entendiste 😣😥

⭐️⭐️⭐️Divide y conquista.⭐️⭐️⭐️

El ordenamiento por mezcla creado por John von Neumann el cual aplica el concepto de “divide y conquista”. Primero divide una lista en partes iguales hasta que quedan sublistas de 1 o 0 elementos. Luego las recombina en forma ordenada.

El profesor viendo como intentas entender su algoritmo.

Pd: Llevo horas aun no entiendo a detalle el codigo.

Entendia como funciona el ordenamiento pro mezcla pero no entendia como funcionaba el programa en python.

solo con la opcion “run and debug” y ver paso por paso como funciona el programa pude entender lo que hacia el codigo

Esta super complejo este tipo de ordenamiento pero comparto lo que yo entendi del algoritmo que se planteo:

lista = [75, 74, 32, 83, 99, 14, 47, 61, 82, 19]

1 .- Recibe la lista y las divide a la mitad,
[75, 74, 32, 83, 99] ***** [14, 47, 61, 82, 19]
2.- crea un una lista nueva con toda la información medio a la izquierda lista[:medio] [75, 74, 32, 83, 99]
3.- crea un una lista nueva con toda la información medio a la derecha lista[medio:] [14, 47, 61, 82, 19]
4.- Luego mediante recursividad le pasa la lista de la izquierda, repitiendo el paso 1, 2 y 3.
[75, 74, 32, 83, 99], paso 1, 2 y 3 [75, 74] ***** [32, 83, 99],
5 .- se queda con la lista mas pequeña y le aplica la comparación para ordenarlos. [74, 75]
6.- luego la lista de la derecha [32, 83, 99] le aplica el paso 1,2 y 3 [32] ***** [83, 99] y luego le aplica el paso 5 nuevamente [83, 99] y los ordena [83, 99] en este caso los deja igual
7.- ya al final los empieza a unir comparandolos nuevamente [32, 74, 75, 83, 99] hasta devolverlos ordenados

MultiFrames!!!

llevo mas de 24 leyendo, modificando y tratando de comprender esto código, hasta ahora lo que me ha resultado mas útil es debugearlo paso a paso.

al principio me costaba comprender porque el código se seguía ejecutando aun después de llegar a la línea final y ahora comienzo a comprender como y cuando se generan los diferentes frames me doy cuenta que es la línea de ese frame en particular y que cada vez que eso sucede ( llegar a la línea final, que sucede una vez alcanzado el caso base ), la ejecución desciende al frame anterior , donde todo el código se ejecuta nuevamente

La explicación la da el profesor a partir del minuto 17:52, lo interesante es interiorizar el concepto!

tuve que ver el video varias veces 🤯

Lo terminé de entender perfectamente con este video

Recomiendo usar el debugger de vscode para ir paso a paso y entender mejor el algoritmo. También tener en cuenta que el código del profesor está mutando la lista original lo que lo hace un poco más difícil de entender.

Aquí dejo una versión que no muta la lista original por si les ayuda:

import random

def ordenamiento_por_mezcla(lista):
    sorted_list = lista[:] # copiar la lista
    if len(sorted_list) > 1:
        medio = len(sorted_list) // 2
        izquierda = sorted_list[:medio]
        derecha = sorted_list[medio:]
        print(izquierda, '*' * 5, derecha)

        # llamada recursiva en cada mitad
        izquierda = ordenamiento_por_mezcla(izquierda) # obtener lista ordenada
        derecha = ordenamiento_por_mezcla(derecha) # obtener lista ordenada

        # Iteradores para recorrer las dos sublistas
        i = 0
        j = 0
        # Iterador para la lista principal
        k = 0

        while i < len(izquierda) and j < len(derecha):
            if izquierda[i] < derecha[j]:
                sorted_list[k] = izquierda[i]
                i += 1
            else:
                sorted_list[k] = derecha[j]
                j += 1

            k += 1

        while i < len(izquierda):
            sorted_list[k] = izquierda[i]
            i += 1
            k +=1

        while j < len(derecha):
            sorted_list[k] = derecha[j]
            j += 1
            k += 1
        
        print(f'izquierda {izquierda}, derecha {derecha}')
        print(sorted_list)
        print('-' * 50)

    return sorted_list


if __name__ == '__main__':
    tamano_de_lista = int(input('De que tamano sera la lista? '))

    lista = [random.randint(0, 100) for i in range(tamano_de_lista)]
    print(lista)
    print('-' * 20)

    lista_ordenada = ordenamiento_por_mezcla(lista)
    print(lista_ordenada)

Sigo recomendando este enlace, tiene todos los tipos de ordenamiento con codigo y paso a paso
https://visualgo.net/es/sorting

Para repasar Recursividad 😃
https://www.enjoyalgorithms.com/blog/recursion-explained-how-recursion-works-in-programming

John von Neumann

Si no entienden el código, puede ser porque no comprenden la recursividad, aquí un video que la explica a la perfección: https://www.youtube.com/watch?v=0NBPd81uhJE

Algo que a mi me ayudo mucho a entender mejor el proceso del algoritmo fue debuggearlo, asi pude ir viendo paso a paso que es lo que iba sucediendo. recomiendo mucho Vs code para debuggear ya que la herramienta que trae es muy intuitiva.

Tre mendo, yo solo tengo una pregunta: ¿Qué estaba pensando la persona que creo esto?

💡 Partiendo del código presentado en clase, hice una versión donde solo se necesita un while (siendo un algoritmo mas eficiente), menos lineas de código, y a mi parecer puede ser un poco más entendible.

Aca esta el repositorio en GitHub con los dos archivos de cada version: La version de la calse (en ingles) y la version mejorada
https://github.com/Giosorio/merge_sort

también dejo el código en la version español:

import random 

def ordenamiendo_por_mezcla(lista):
    if len(lista) > 1:
        medio = len(lista)//2
        izquierda = lista[:medio]
        derecha = lista[medio:]
        
        # Print the process 
        # print(izquierda, '*' * 5, derecha)

        # Llamada recursiva en cada mitad
        izquierda = ordenamiendo_por_mezcla(izquierda)
        derecha = ordenamiendo_por_mezcla(derecha)

        
        lista = []
        while len(izquierda) != 0 and len(derecha) != 0:
            if izquierda[0] < derecha[0]:
                lista.append(izquierda.pop(0))
            else:
                lista.append(derecha.pop(0))


        if len(izquierda) > 0:
            lista += izquierda
        else:
            lista += derecha
        
        
        # Print the process 
        # print('izquierda {}, derecha {}'.format(izquierda, derecha))
        # print(lista)
        # print('-' * 5)

    return lista 




if __name__ == '__main__':
    tamano_de_lista = int(input('Tamano de lista: '))

    lista = [random.randint(0, 100) for i in range(tamano_de_lista)]
    # lista = [3, 41, 11, 84, 25]
    print(lista)
    print('-' * 5)

    lista_ordenada = ordenamiendo_por_mezcla(lista)
    print(lista_ordenada)

el merge sort, es n log n

El hecho de dividir dentro del proceso de un algoritmo, hace que este tenga una notación de log de n.

El merge sort, lo inventó Jhon Vonn Numann.

Lo que hacemos en el merge sort, es dividir al punto mínimo la lista, en una lista de longitud 1, por lo que apartir de ahí podemos empezar a comparar hasta llegar a la lista completamente ordenada.

Nuevamente, uno de los algoritmos más poderosos, utilizan la estrategia de divide y conquista.