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…

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

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.

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)

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é.

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

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

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

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

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.

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

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/

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

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

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/

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

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

Les comparto la explicación de ChatGPT WOW

¡Por supuesto! El código que has compartido implementa el algoritmo de ordenamiento por mezcla (merge sort) de manera recursiva. Este algoritmo divide la lista en mitades más pequeñas, ordena esas mitades y luego las combina en una lista ordenada. Aquí tienes una explicación paso a paso de cómo funciona el código:

1. Se importa el módulo random, que se utilizará para generar números aleatorios.

1. Se define la función ordenamiento_por_mezcla(lista) que implementa el algoritmo de ordenamiento por mezcla. Esta función toma una lista como entrada y la ordena.

1. La función comienza verificando si la longitud de la lista es mayor que 1. Si la longitud es 1 o menor, la lista se considera ordenada y se retorna tal cual.

1. Si la longitud es mayor que 1, la función encuentra el punto medio de la lista (medio) y divide la lista en dos partes: izquierda y derecha.

1. Luego, la función imprime las sublistas izquierda y derecha para mostrar cómo se están dividiendo en cada iteración.

1. Se realiza una llamada recursiva a ordenamiento_por_mezcla(izquierda) para ordenar la mitad izquierda de la lista, y otra llamada recursiva a ordenamiento_por_mezcla(derecha) para ordenar la mitad derecha de la lista.

1. Después de que ambas mitades estén ordenadas, se realiza el proceso de fusión (merge) de las dos mitades ordenadas en una lista ordenada completa.

1. Se utilizan tres iteradores: i para la mitad izquierda, j para la mitad derecha y k para la posición en la lista principal.

1. Se compara el elemento actual en las sublistas izquierda[i] y derecha[j], y se coloca el elemento más pequeño en la posición k de la lista principal. Luego, se incrementa el iterador correspondiente y el iterador k.

1. Se repite el paso 9 hasta que se hayan recorrido completamente ambas sublistas.

1. Si aún quedan elementos en alguna de las sublistas después de salir del bucle anterior, se agregan a la lista principal.

1. Finalmente, se imprime el estado de las sublistas izquierda y derecha, la lista principal ordenada y una línea de guiones para separar visualmente los resultados.

1. La función retorna la lista principal ordenada.

1. En la parte final del código, se verifica si el script se está ejecutando como el programa principal (no importado como módulo). Se solicita al usuario ingresar el tamaño de la lista a ordenar.

1. Se crea una lista llamada lista que contiene números aleatorios entre 0 y 100. La cantidad de números en la lista es igual al tamaño especificado por el usuario.

1. Se imprime la lista original.

1. Se llama a la función ordenamiento_por_mezcla(lista) para ordenar la lista.

1. Se imprime la lista ordenada resultante.

En resumen, este código implementa el algoritmo de ordenamiento por mezcla utilizando recursión para dividir y combinar sublistas, lo que resulta en una lista principal ordenada al final.

En la clase de Recursividad del curso anterior un compañero esta pagina, es muy buena ya que te permite ver cada paso del código y como se va ejecutando. Solo debes meter el código y ejecutar.

https://pythontutor.com/visualize.html#mode=edit

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.

📢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 😣😥

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

Explicación gráfica de los pasos:

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😅

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.

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?

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

aqui un video que te explica como ordenar

https://youtu.be/-U4asqJ4ff4?si=3QdsB-SBG6HoMRIY

Me llegué a frustrar con esta clase, pero llegué a comprenderlo en el 5 intento, luego de 12 horas de dedicación y hablando mucho en voz alta 😄.

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

He estado leyendo muchos comentarios de que este tema es super difícil, o que no entienden. Lo mejor que pueden hacer es ir a YouTube y ver varios videos antes de llegar aquí. Este profesor es excelente pero tiende a complicar alguos temas.

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

💡 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)

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 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?

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

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 =)

entiendes recursividad y es como dar un paso mas en tu logica de progrmacion increible!!

Por alguna extraña razón me llevo bien con los comprenhensions, lo entendía el ejercicio, así que lo hice yo mismo. Hasta que uno no comienza a hacerlo no se comprende del todo. Aqui, lo hice más fácil.

import random

def merge_sort(list):
    if len(list) <= 1:
        return list
    
    # Divide la lista en dos mitades
    mid = len(list) // 2
    left = merge_sort(list[:mid])
    right = merge_sort(list[mid:])
    print(f'left: {left} right: {right}')
    print('-' * 20)

    # Inicializa una lista vacía para almacenar el resultado antes "K"
    result = []
    
    # Inicializa índices para recorrer las dos mitades
    i = j = 0

    # Combinación de las dos mitades ordenadas
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    # Agrega los elementos restantes, si los hay
    result.extend(left[i:])
    result.extend(right[j:])

    # Devuelve la lista ordenada
    print(f'  =>result: {result}')
    print('_' * 20)
    return result

if __name__ == '__main__':
    list_size = int(input("Enter list size: "))
    list = ([random.randint(0, 100) for _ in range(list_size)])
    print(list)
    print('-' * 20)


    list_sort = merge_sort(list)
    print(list_sort)

El algoritmo de ordenamiento por mezcla (Merge Sort) es un algoritmo de ordenamiento eficiente que utiliza la estrategia “divide y conquista” para ordenar una lista de elementos. A diferencia del algoritmo de ordenamiento de burbuja, el ordenamiento por mezcla es mucho más eficiente y se adapta bien a listas grandes. Aquí tienes una descripción del algoritmo de ordenamiento por mezcla:

Ordenamiento por Mezcla (Merge Sort):

• Descripción: El algoritmo de ordenamiento por mezcla divide la lista en dos mitades de manera recursiva, hasta que cada mitad esté compuesta por un solo elemento. Luego, combina las mitades ordenadas para crear una nueva lista ordenada. La combinación se realiza de manera ordenada, comparando elementos de ambas mitades y seleccionando el menor en cada paso.
• Utilidad: El ordenamiento por mezcla es uno de los algoritmos de ordenamiento más eficientes y se utiliza en aplicaciones del mundo real. Su eficiencia radica en su capacidad para dividir y combinar eficazmente las listas, lo que resulta en un tiempo de ejecución O(n log n) en el peor caso.
• Complejidad Temporal: La complejidad temporal en el peor caso del ordenamiento por mezcla es O(n log n), donde “n” es el número de elementos en la lista. Esto lo hace adecuado para listas de cualquier tamaño y es uno de los algoritmos de ordenamiento más eficientes.

tener estos ejemplos gráficos es de lo mejor

Como quiera no hay nada más difícil de entender, que… “LAS MUJERES”

“al ser recursiva, y volverse mas pequeña, sera un crecimiento logarítmico” Excelente dato.
.
No se si sea porque ya he visto este algoritmo en los otros cursos pero a este profe se le entiende genial.

Claves que me ayudaron a entender el algoritmo:

1. El orden en el cual se va ejecutando la recursividad, cada llamada a la función se va acumulando hasta llegar al caso base que es el primer if del código, a partir de ese puntos se empiezan a ejecutar de la última a la primera llamada.

2. Al pasar el array por parametro esto implica que cualquier modificación a dicho array se va reflejar en la función que lo envío.

3. En el primer while uno de las dos partes se va recorrer completamente, por lo cual los otros whiles son agregar los elementos que no se recorrieron. Sólo uno de los dos siguientes whiles se va a ejecutar.

Solo entiendan el concepto, el algoritmo siempre será el mismo y lo podemos replicar de algún lado. No es necesario que ustedes lo tengan que codear desde cero.

"La derecha es más grande que la izquierda"
En código sería:

if right[j] > left[i]

Lo correcto sería decir…
"La derecha es menor que la izquierda"
En código sería:

if right[j] < left[i]

Ahora sabiendo esto, cuando aplicamos el “else” lo correcto sería decir.
“La derecha es menor que la izquierda”

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[i]
                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('_'* 100)

        return lista

if __name__ =='__main__':
    tamaño_de_lista = int(input("De que tamaño sera la lista?"))
   
    lista = [random.randint(0, 100) for i in range(tamaño_de_lista)]
    print(f"Lista Desordenada = {lista}")
    print('_' * 100)

    lista_ordenada = ordenamiento_por_mezcla(lista)
    print(f"Lista Ordenada = {lista_ordenada}")

Aca les comparto mi código con comentarios de como logre entender este algoritmo, espero que les sea de utilidad, animo gente cada dia nos volvemos más valiosos con aprender constantemente 😄

"""Con este algoritmo (de O(n log n))vamos dividiendo listas constantemente hasta que solo tengan 1 valor cada una (usando Recursividad) y luego las comparamos y ordenamos. Vamos de listas largas a listas cortas y luego las vamos ordenando desde las listas cortas hasta las lista largas. Recuerda: Divide y Conquista"""

import random

def ordenamiento_por_mezcla(lista):
    """Esta parte de la función tiene complejidad algoritmica de 'O(log n)'"""
    if len(lista) > 1:                                          # Si la lista es de 1 elemento entonces por definicion ya esta ordenada
        medio = len(lista) // 2
        # Aplicamos "slicing", creamos 2 listas
        izquierda = lista[:medio]                               # Dividimos una lista a la mitad (valor de "medio"), es el lado izquierdo
        derecha = lista[medio:]                                 # Hacemos otra lista pero que comienza del valor de "medio"
        print(izquierda, '*' * 5, derecha)                      # Imprimimos los valores de las 2 listas, (se imprime varias veces)

        # Aplicamos recursividad en cada mitad, se ejecutan hasta que solo quedan lista de solo 1 valor
        ordenamiento_por_mezcla(izquierda)                      # Mandamos lista "izquierda" como parametro a la funcion con recursividad y se ejecuta
        ordenamiento_por_mezcla(derecha)                        # Mandamos lista "derecha" como parametro a la funcion con recursividad y se ejecuta

        # Iteradores para recorrer las 2 sublistas
        i = 0   # lista "izquierda"                             # Esto servirá bastante cuando las listas sean mas largas para compararlo con el valor de la lista del otro lados
        j = 0   # lista "derecha"                               # Esto servirá bastante cuando las listas sean mas largas para compararlo con el valor de la lista del otro lados
        # Iterador para la lista principal
        k = 0   # lista "lista", sera el indice de la lista principal

        """Esta parte de la función tiene complejidad algoritmica de 'O(n)'"""
        # Ciclo para compara el valor de la izquierda con el de la derecha
        while i < len(izquierda) and j < len(derecha):
            if izquierda[i] < derecha[j]:
                lista[k] = izquierda[i]                         # El valor de la izquierda es menor al de la derecha, la agregamos a lista principal
                i += 1
            else: 
                lista[k] = derecha[j]                           # Paso el valor de la derecha a la izquierda porque es menor al valor de la derecha
                j += 1                                          

            k += 1                                              # Aumentas "k", que seria el indice de la lista principal
        
        # Solo uno de los dos siguentes ciclos se cumplira
        # Ciclo para
        while i < len(izquierda):
            lista[k] = izquierda[i]                             # Guardamos el valor mayor a la siguiente posición (atras aplicamos "k += 1") ahora "k" vale una posicion más
            i += 1
            k += 1                                              # Independientemente del resultado "k" siempre aumentara su valor por 1

        while j < len(derecha):                                 # Guardamos el valor mayor a la siguiente posición (atras aplicamos "k += 1") ahora "k" vale una posicion más
            lista[k] = derecha[j]
            j += 1      
            k += 1                                              # Independientemente del resultado "k" siempre aumentara su valor por 1

        print(f'izquierda {izquierda}, derecha {derecha}')          # Imprimimos la lista de "izquierda" y la de "derecha"
        print(f'Porción de lista ordenada: \n{lista}')            
        print('-' * 35)

    return lista


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

    lista = [random.randint(0, 9) for i in range(list_size)]
    print(f'Lista desordenada: \n{lista}  \n{"-" * 35}')

    lista_ordenada = ordenamiento_por_mezcla(lista)
    print(f'Lista ordenada: \n{lista_ordenada}')
    

Hacerlo en papel y ver los prints me hizo entenderlo mucho mejor.

import random


def selectAlgorithm(option):
    list_data = addInsertData()
    print(list_data)
    sorted_list =  SortedList(list_data)

    if option == 1:
        print("option 1")
        sorted_data = sorted_list.order_by_insert()
    if option == 2:
        sorted_data = sorted_list.order_for_mixing(sorted_list.list_data)

    return sorted_data


def addInsertData():
    lower_rank = int(input('Write lower rank: '))
    top_rank = int(input("Write top rank: "))
    size_data = int(input("Write size of data: "))

    list_data = [random.randint(lower_rank,top_rank) for i in range(size_data)  ]

    return list_data


class SortedList:

    def __init__(self, list_data):
        self.list_data = list_data


    def order_by_insert(self):
        for index in range(1, len(self.list_data)):
            current_value = self.list_data[index]#14
            current_posicion = index
            while current_posicion > 0 and self.list_data[current_posicion - 1 ] > current_value:
                self.list_data[current_posicion] = self.list_data[current_posicion -1]
                current_posicion -= 1

            self.list_data[current_posicion] = current_value

        return self.list_data


    def order_for_mixing(self, list_data):
        if len(list_data) > 1:
            medium = len(list_data) // 2
            left = list_data[:medium]
            rigth = list_data[medium:]
            
            #call og the same function in each half data of data
            self.order_for_mixing(left)
            self.order_for_mixing(rigth)

            #iterator run two sub-lists
            i = 0
            j = 0
            # iterator by principal list
            k = 0

            # compare tow list
            while i < len(left) and j < len(rigth):
                if left[i] < rigth[j]:
                    list_data[k] = left[i]
                    i +=1
                else:
                    list_data[k] = rigth[j]
                    j += 1

                k += 1

            while i < len(left):
                list_data[k] = left[i]
                i += 1
                k += 1

            while j < len(rigth):
                list_data[k] = rigth[j]
                j += 1
                k += 1            
        
        return list_data



if __name__ == '__main__':
    option = int(input(
    """Insert option.
    \n1. Order by insert.
    \n2. Order by mixin.
    \noption
    """))
    
    list_data = selectAlgorithm(option)
    print("list data: ", list_data)

Un concepto clave para entender recursividad es la pila de llamadas. Cada que se hace una llamada en una función recursiva hacemos
"push" de esa función (la guardamos, pero no hemos retornado su valor) a la pila de llamadas hasta que llegamos el caso base y retornamos el primer valor. Con el primer valor de retorno hacemos “pop” a la pila y evaluamos la primera función de la pila (la última que entró) con ese valor. Repetimos el proceso hasta que la pila esté vacía.

Wow, parece magia, es increíble :0

Les recomiendo que debugueen el codigo, pueden ver paso a paso como avanzan los iteradores y se producen los swapping. A mi me ayudo a entender el algoritmo, yo que uso pycharm marque las casillas importantes, y fui avanzando el codigo poco a poco.

Intenté hacer el código con solo la explicación del algoritmo y sin ver el resultado del profesor, me costó dos viajes a casa del camión en estarlo pensando pero funciona sin recursividad, dejo las líneas:

import random

def merge_sort(lista):
    n = len(lista)
    listSorted = []
    i = 0
    length = 0
    #Mientras el tamaño de las particiones no exceda el tamaño de la lista
    while length < n:
        #tamaño de las sublistas que se envian empieza [1,2,4...]
        length = 2**i
        index = 0
        while index < n:
            #Lista izquierda y derecha
            listL=[] 
            listR=[]
            if index+length <= n:
                listL = lista[index:index+length]
            else:
                listL = lista[index:n]
            if index + (2*length) <= n:
                listR = lista[index+length:index+(2*length)]
            else:
                listR = lista[index+length:n]
            index = index + (2*length)
            subSorted = ordenaListas(listL,listR)
            ##Vacía la lista subordenada en la lista ordenada poco a poco
            for k in range(len(subSorted)):
                listSorted.append(subSorted[k])
        #la lista final ordenada se vuelve la lista a particionar
        lista = listSorted.copy()
        listSorted.clear()
        i=i+1
    return lista


def ordenaListas(listL,listR):
    indexA = 0
    indexB = 0
    merged = []
    lenA= len(listL)
    lenB= len(listR)
    #La lógica es toma un índice izquierdo y uno derecho y avanza dependiendo de cual número baja
    #al arreglo ordenado hasta que estan abajo todos los de un lado
    while indexA<lenA and indexB<lenB:
        if listL[indexA]>listR[indexB]:
            merged.append(listR[indexB])
            indexB=indexB+1
        else:
            merged.append(listL[indexA])
            indexA=indexA+1
    #Si sobran datos de lado izquierdo los baja
    for i in range (indexA,len(listL)):
        merged.append(listL[i])
    #si sobran datos de lado derecho los baja
    for i in range (indexB,len(listR)):
        merged.append(listR[i])
    return merged

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 inicial:\n",lista)
    lista_ordenada = merge_sort(lista)
    print("Lista ordenada:\n",lista_ordenada)

Si les pasa como a mi que no me había quedado muy claro que son las llamadas recursivas, acá les dejo un post que me ayudo a entenderlo mejor.
https://www.tutorialesprogramacionya.com/pythonya/detalleconcepto.php?punto=90&codigo=91&inicio=75

Lo que entiendo que realiza este Ordenamiento, es que va por pares de numeros comparando hasta llegar a la lista final de forma ordenada, y esa comparación va como mejor le convenga

https://pythontutor.com/render.html#mode=display

Pueden chequear paso por paso su algoritmo, en este caso, son 297 pasos pero ayuda bastante a entender que pasa en cada paso.

Saludos!

No me costo mucho entenderlo ya que utilize el debug de visual studio y a medida que iba paso a paso lo trataba de seguir con mi cuaderno de anotaciones, más los gif que compartieron los compañeros de esa manera todo se torno más claro.

Lo que comprendí es que el algoritmo toma una lista y la divide en 2 partes enteras, de manera recursiva, hace lo mismo para cada una de las 2 primeras sublistas.
y luego evalua los valores y los va ordenando uno a uno en cada una de esas sublistas (la de la izquierda y la derecha)
al final devuelve todo ordenado.