[0:00]MergeSort o ordenamiento por mezcla es un método externo y estable. Recibe una lista desordenada y su función es ordenarla. Realiza tres pasos para ordenar la lista: primero, ordena la mitad izquierda, luego la mitad derecha, y por último, mezcla ambas listas ordenadas para conseguir la lista total ordenada. Los pasos uno y dos ordenan una lista para lo cual se usará el mismo MergeSort de forma recursiva. Poniendo más detalles vemos que el módulo MergeSort recibe una lista para ser ordenada. Luego, ordena la parte izquierda de dicha lista y a continuación la parte derecha. Por último, mezcla ambas listas para obtener toda la lista ordenada. Analicemos en detalle cómo funciona MergeSort. Supongamos que recibe una lista de 10 elementos para ser ordenada. Entonces, lo primero que hace es dividir la lista en dos partes iguales y ordenar la lista de la izquierda llamándose a sí misma recursivamente. La nueva instancia de MergeSort recibe una lista de cinco elementos. Toma la parte izquierda de la misma. Cuando la misma tenga tamaño impar, vamos a suponer que la lista de la izquierda tiene un elemento menos que la de la derecha y se invoca recursivamente. Así, continúa el proceso de llamados recursivos, recibiendo cada vez una lista más pequeña hasta llegar a recibir una con un único elemento. Aquí nos detengamos y consideremos que los tres pasos de MergeSort tienen como objetivo ordenar la lista recibida. Entonces, en este caso, en que la lista tiene un único elemento, ¿tiene sentido ejecutarlos? Claro que no. La lista ya está ordenada. Este será el caso base que detenga la recursividad, siendo los pasos 1, 2 y 3 necesarios solo para las listas que tengan dos elementos o más. Agregamos esto al pseudocódigo. Entonces, al recibir una lista de un elemento, MergeSort sabe que no debe realizar ninguna tarea, por lo cual finaliza. Pintamos la lista de verde indicando que está ordenada. Y finaliza el proceso MergeSort habiendo ordenado una lista de tamaño uno. El siguiente paso es aplicar MergeSort a la lista de la derecha, que por tener un único elemento, está ordenada y se comporta como vimos anteriormente. En este punto, MergeSort ha ordenado la lista de la izquierda y la lista de la derecha, pero la lista completa continúa desordenada. El paso tres se encarga de mezclar las dos listas ordenadas, generando una lista completa ordenada, y así finaliza MergeSort, ordenando una lista de dos elementos, que es la lista izquierda del llamado anterior. Ahora MergeSort debe ordenar la lista de la derecha que se pinta en rojo indicando que está desordenada. La divide en dos y debe ordenar la lista de la izquierda, que por tener un único elemento, procederá como ya vimos. Luego debe ordenar la lista de la derecha que tiene dos elementos y se ordenará también como hemos visto anteriormente. Nuevamente tenemos dos listas ordenadas, pero la lista completa desordenada. Con el paso 3 se mezclan ambas listas para obtener la lista completa de tres elementos ordenada, que corresponde a la lista derecha del llamado anterior. El flujo retorna y a continuación se deben mezclar las dos listas ordenadas, generando una lista completa ordenada. Por ahora no importa cómo el módulo mezclar realiza su tarea, luego lo analizaremos en detalle. Y así, MergeSort ha ordenado una lista de cinco elementos, que corresponde a la mitad de nuestra lista original. El siguiente paso es ordenar la lista de la derecha, donde MergeSort procederá igual que con la lista de la izquierda. Por último, mezclará estas dos listas de cinco elementos, generando la lista final de 10 elementos ordenada. Vamos a poner más detalles de implementación. La lista será recibida como un parámetro por referencia para que los cambios realizados dentro de MergeSort se reflejen en la lista original. Representamos esto con un asterisco.
[4:59]La lista se recibe completa la primera vez, pero luego MergeSort necesita recibir la mitad izquierda o la mitad derecha o de la mitad derecha, la mitad izquierda y así. Por lo que requiere recibir sublistas. Representaremos esto con dos parámetros que indiquen el inicio y el fin de la sublista. Que la lista tenga dos elementos o más lo vamos a representar con la condición de que inicio sea menor que fin. Para representar la mitad izquierda y la mitad derecha, vamos a definir un índice llamado medio que será la mitad entre inicio y fin. La lista izquierda será desde Ini hasta medio y la lista derecha desde medio +1 hasta fin. Al módulo mezclar hay que pasarle como parámetros por referencia ambas listas. La izquierda y la derecha que forman la lista total ordenada. Entonces, para la lista izquierda pasamos la lista, inicio y medio. Y para la lista derecha, medio +1 y fin. Pero medio +1 se puede calcular. Por lo que basta con el índice medio. El índice medio hay que calcularlo y debe ser la mitad entre inicio y fin, entonces será el promedio de estos dos. Como es un índice, nos quedamos con la parte entera. Con esto ya tenemos suficiente nivel de detalle como para implementarlo en cualquier lenguaje. Solo falta ver el módulo mezclar. Lo analicemos en detalle. Como nos referimos ahora a su encabezado, indicamos con el asterisco que recibe el parámetro lista por referencia. Recordemos la funcionalidad de este módulo. Recibe dos listas, la lista izquierda va desde inicio hasta medio y la lista derecha desde medio +1 hasta fin. Ambas listas están ordenadas, entonces debe mezclarlas para conseguir la lista total ordenada. Usaremos una lista auxiliar donde se generará la lista ordenada a partir de la mezcla. También índices para recorrer estas listas. El índice izquierda para recorrer la lista izquierda, el que se iniciará en inicio. El índice derecha para recorrer la lista derecha que inicia en medio +1. Y el índice auxiliar para recorrer la lista auxiliar que inicia en cero. La base de este algoritmo es pasar el menor elemento de ambas listas a la lista auxiliar. Como ambas listas están ordenadas, los menores están al inicio de ambas. El menor de estos dos será el menor de todos y se lo pasa a la lista auxiliar. Como en este caso se pasó el elemento de la lista derecha, se incrementa el índice derecha y se repite el procedimiento. También se incrementa el índice de la lista auxiliar para poder recibir el siguiente elemento. Cuando el menor se encuentra en la lista izquierda, se procederá de la misma manera, pasando el elemento a la lista auxiliar e incrementando el índice izquierda y el índice auxiliar. Por ahora el código realiza las inicializaciones y luego, si el elemento de la lista izquierda es menor, lo pasa a la lista auxiliar. Si no, pasa el de la lista derecha. Esto se repetirá en un ciclo, consiguiendo que la lista auxiliar resulte ordenada. En algún momento, alguna de las listas, izquierda o derecha, se habrá procesado completamente y su índice habrá desbordado la lista. Esto impide que continúe el ciclo, por lo cual este deberá ejecutarse mientras ninguno de los índices, ni izquierda ni derecha, haya desbordado. Será mientras izquierda sea menor o igual que medio y derecha menor o igual que fin. Finalizado este ciclo, es porque alguna de las listas se ha procesado completamente, entonces solo queda pasar lo que falta procesar de la otra lista hacia la lista auxiliar. Tal como ocurre en nuestro ejemplo, si la que ha finalizado es la lista izquierda, se copiará lo que falta procesar de la lista derecha hacia la lista auxiliar. Para lo cual se utilizará un índice K que tomará los valores desde derecha hasta fin para así copiar lista sub K hacia lista auxiliar. Si la que ha finalizado es la lista derecha, hay que copiar el final de la lista izquierda. El código es el mismo, pero con K variando desde izquierda hasta medio. Ahora vamos a ver que no son necesarias estas condiciones, ya que si la lista que ha finalizado es la izquierda, se ejecutará el primer ciclo normalmente, pero no el siguiente, ya que medio es menor que izquierda. De igual forma, si finalizó la lista derecha, el primer ciclo no se ejecutará, ya que fin es menor a derecha. Y se ejecutará el segundo ciclo como corresponde. Hasta aquí hemos conseguido ordenar la totalidad de la lista en la lista auxiliar. Solo falta copiarla hacia la lista definitiva, que es donde debe quedar ordenada por haber sido pasada por referencia. Usamos un índice K para recorrer la lista auxiliar desde cero hasta su fin, que es índice auxiliar -1. Y observamos que el elemento que está en la posición K = 0 se debe copiar en la posición inicio. El que está en la posición K = 1, a la posición inicio + 1. En general, el elemento que está en la posición K se copiará a la lista definitiva en la posición inicio + K. Con esto finalizamos el módulo mezclar, que recibe dos listas, izquierda y derecha, contiguas y ordenadas. Luego detecta los menores elementos y los pasa a una lista auxiliar de manera que esta resulta ordenada. Hasta que termina de procesar alguna de las listas, esto lo realiza con el siguiente pseudocódigo. Después copia lo que resta de la otra lista en la auxiliar obteniendo en esta la mezcla ordenada de las dos listas. Por último, copia la lista auxiliar en el espacio ocupado por las dos listas iniciales. El módulo mezclar junto al módulo MergeSort completan el método de ordenamiento. Si te ha gustado la explicación, deja tu like y suscríbete, y lo mejor que puedes hacer por mí es dejarme tu comentario indicando qué es lo que más te ha gustado y qué consideras que podría mejorar. Muchas gracias.
