Algoritmo de ordenación de mezcla
Merge sort
En nuestra sección de algoritmos de ordenamiento hemos visto algunos de los algoritmos más conocidos, pero existen otros que, como veremos, en determinadas situaciones pueden ser mejores.
Uno de esos algoritmos es el de mezcla o "merge sort".
Se trata de otro algoritmo recursivo, parecido a quicksort, aunque con un enfoque algo diferente.
Empezaremos por dividir la lista de los elementos a ordenar en dos listas de tamaños similares:
33 36 27 15 43 35 36 42 33 36 27 15 43 35 36 42
Después aplicaremos el mismo método recursivamente para cada una de las sublistas:
33 36 27 15 43 35 36 42
33 36 27 15 43 35 36 42
33 36 27 15 43 35 36 42
33 36 27 15 43 35 36 42
Cuando el número de elementos de una sublista sea cero o uno, la sublista está ordenada.
En este punto es cuando empieza realmente la mezcla, retrocediendo en el procedimiento recursivo.
Empezamos por comparar los primeros elementos de cada sublista, tomando el menor de ellos, y pasando al siguiente elemento de la sublista correspondiente. Por ejemplo, entre 33 y 36, tomamos el 33. Como la sublista izquierda sólo tiene un elemento, añadiremos el resto de los elementos de la sublista derecha. En este caso el 36. Haremos lo mismo con el resto de secciones:
33 36 15 27 35 43 36 42
Ahora tenemos sublistas de dos elementos, pero el algoritmo de mezcla es el mismo. Comparamos 33 y 15, tomamos el 15. Ahora comparamos 33 y 27, y tomamos el 27. La sublista derecha se ha consumido, así que añadimos los elementos de la sublista izauierda: 33 y 36. Lo mismo con el resto de secciones:
15 27 33 36 35 36 42 43
Y así suscesivamente:
15 27 33 35 36 36 42 43
En la práctica no crearemos todas las sublistas, ya que requeriría el uso de mucha memoria, sobre todo si la lista es muy grande. En su lugar sólo guardaremos los índices de los extremos izquierdo y derecho:
33 36 27 15 43 35 36 42 ^ ^ ^ I=0 C=4 D=7 33 36 27 15 43 35 36 42 ^ ^ ^ ^ ^ ^ I=0 C=2 D=3 I=4 C=6 D=7 33 36 27 15 43 35 36 42 ^ ^ ^ ^ ^ ^ ^ ^ 0 1 2 3 4 5 6 7 33 36 27 15 43 35 36 42
A la hora de mezclar, sin embargo, sí será necesario crear listas auxiliares, ya que el resultado de la mezcla se debe almacenar en una lista diferente a la de las listas a mezclar. Lo más eficiente, para evitar operaciones de copia, es crear dos listas con los elementos a mezclar, y guardar el resultado de la mezcla en la lista original.
En la última etapa crearemos dos listas I, y D, con un elemento cada una: 33 y 36. Esas listas, una vez acabada la mezcla, se destruyen y se repite el proceso para cada tramo a mezclar.
En al última mezcla crearemos dos listas I y D, con cuatro elementos cada una: 15, 27, 33, 36 y 35, 36, 42, 43.
Por lo tanto, el tamaño necesario para almacenar elementos en listas auxiliares será el mismo que el de la lista a ordenar.
Por supuesto, también hay un consumo de memoria debido al uso de algoritmos recursivos, que será tanto mayor cuanto más elementos contenga la lista a ordenar.
Ejemplo para ordenar vectores
Aunque no es el mejor algoritmo para ordenar vectores, se puede usar, y es relativamente sencillo de implementar.
#include <iostream>
#include <cstdlib>
#include <vector>
void Mezclar(std::vector<int>& lis, int izq, int cen, int der) {
int n1 = cen - izq + 1; // Nº de elementos en la mitad izquierda
int n2 = der - cen; // Nº de elementos en la mitad derecha
// Necesitamos dos listas temporales
std::vector<int> I(n1), D(n2);
for (int i = 0; i < n1; i++) I[i] = lis[izq + i];
for (int i = 0; i < n2; i++) D[i] = lis[cen + 1 + i];
int i = 0, j = 0; // Índices para recorrer las dos sublistas
int k = izq; // punto de inserción de la mezcla
// Mezclamos las dos sublistas en lis[izq] a lis[der]
while (i < n1 && j < n2) {
if (I[i] <= D[j]) {
lis[k] = I[i];
i++;
}
else {
lis[k] = D[j];
j++;
}
k++;
}
// Copiar los elementos que quedan en la sublista izquierda
while (i < n1) {
lis[k] = I[i];
i++;
k++;
}
// Copiar los elementos que quedan en la sublista derecha
while (j < n2) {
lis[k] = D[j];
j++;
k++;
}
}
void OrdenarMezcla(std::vector<int>& lis, int izq, int der){
if (izq >= der) return; // Una lista con cero o un elemento está ordenada
int cen = izq + (der - izq) / 2; // Calcular el centro
OrdenarMezcla(lis, izq, cen); // Ordenar recursivamente la mitad izquierda
OrdenarMezcla(lis, cen + 1, der); // Ordenar recursivamente la mitad derecha
Mezclar(lis, izq, cen, der); // Mezclar
}
int main() {
// Algoritmo de ordenación por mezcla o merge sort
std::vector<int> lista;
for(int i=0; i<20; i++) lista.push_back(std::rand()%100);
for(int i=0; i<lista.size(); i++) std::cout << lista[i] << ",";
std::cout << std::endl;
OrdenarMezcla(lista, 0, lista.size()-1);
for(int i=0; i<lista.size(); i++) std::cout << lista[i] << ",";
std::cout << std::endl;
return 0;
}
Ordenar listas enlazadas
Para ordenar arrays o vectores es preferible usar otros algoritmos, como "quick sort", Sin embargo, dónde mejor funciona el algoritmo de mezcla es a la hora de ordenar listas enlazadas, a las que no se puede aplicar ese algoritmo, ya que no disponen de acceso aleatorio a sus elementos.
Vamos a crear una variante de la clase de listas enlazadas con plantillas que incorpora un método para ordenarla.
Nos basaremos en el código del curso de EDD, al que añadiremos algunos datos miembro y métodos.
Para optimizar las inserción de elementos al final de la lista añadiremos un puntero al último elemento de la lista.
También añadiremos un entero que almacenará el número de elementos que contiene la lista.
int cuenta;
Nodo<DATO> *ultimo;
En ambos casos es posible calcular esos valores, pero es más eficiente mantener esos valores que calcularlos cada vez que sea necesario hacer uso de ellos.
Aplicar el algoritmo de mezcla a una lista enlazada no es tan simple como hacerlo con un vector o un array.
La idea es mover los nodos existentes en la lista enlazada, y no crear nuevos o hacer copias de los existentes.
Para ello tendremos que tener en cuenta algunos detalles para no perder el acceso a determinados nodos, y no destruir nodos antes de tiempo.
Por supuesto, si la lista está vacía o contiene un único nodo, ya está ordenada.
La primera parte del algoritmo consiste en dividir la lista en dos. para ello crearemos un método privado "Separar", que dividirá la lista actual y devolverá una lista con la segunda mitad de la lista original.
template<class DATO>
Lista<DATO> Lista<DATO>::Separar(int n) {
Lista<DATO> retval;
if(n>cuenta) return retval;
Nodo<DATO> *temp = primero;
int i=0;
while(i++<n-1) temp = temp->siguiente;
retval.primero = temp->siguiente;
retval.cuenta = cuenta-n;
retval.ultimo = ultimo;
cuenta = n;
ultimo = temp;
temp->siguiente = nullptr;
return retval;
}
Una vez dividida la lista en dos partes, llamaremos al método de ordenar recursivamente con cada mitad de la lista.
Finalmente mezclaremos las dos listas ordenadas.
template<class DATO>
void Lista<DATO>::OrdenarMezcla() {
if(cuenta<=1) return; // Una lista con cero o un elemento está ordenada
int n = cuenta/2; // Calcular el centro
Lista<DATO> lista2 = Separar(n);
OrdenarMezcla(); // Ordenar recursivamente la mitad izquierda
lista2.OrdenarMezcla(); // Ordenar recursivamente la mitad derecha
Mezclar(lista2); // Mezclar
lista2.primero=nullptr;
}
El método para mezclar dos listas es similar al que vimos para los arrays, pero con algunas diferencias importantes.
Ahora no necesitamos copiar los elementos de las dos listas a mezclar. En su lugar usaremos una lista temporal, a la que iremos añadiendo los nodos de cada lista a mezclar, en el orden correcto.
Los nodos no se copian, sencillamente creamos una nueva lista con los nodos de las dos listas originales, sin destruir esas listas. Cada uno de los nodos pertenece a dos listas: la temporal con la mezcla y las originales.
Para ello usaremos el método privado AgregarNodo,que inserta la final de la lista el nodo indicado, sin modificarlo de ninguna manera.
template<class DATO>
void Lista<DATO>::AgregarNodo(Nodo<DATO>* nodo) {
if(ultimo) {
ultimo->siguiente=nodo;
ultimo = nodo;
} else {
primero = ultimo = nodo;
}
cuenta++;
}
Empezaremos agregando el menor de cada nodo de las dos listas, hasta que una de ellas se acabe, Y después añadiremos el resto de la lista que aún contenga elementos.
Como los nodos no se eliminan de las listas de entrada, lo que haremos es mover el puntero "primero" a medida que se extraigan nodos de una lista.
template<class DATO>
void Lista<DATO>::Mezclar(Lista<DATO> lista2) {
// Necesitamos una lista temporal
Lista<DATO> temp;
// Mezclamos las dos sublistas *this y lista2
while(primero && lista2.primero) {
if(primero->dato <= lista2.primero->dato) {
temp.AgregarNodo(primero);
primero = primero->siguiente;
} else {
temp.AgregarNodo(lista2.primero);
lista2.primero = lista2.primero->siguiente;
}
}
// Copiar los elementos que quedan en la lista *this
while(primero) {
temp.AgregarNodo(primero);
primero = primero->siguiente;
}
// Copiar los elementos que quedan en la lista2
while(lista2.primero) {
temp.AgregarNodo(lista2.primero);
lista2.primero = lista2.primero->siguiente;
}
// La lista *this ahora contiene la mezcla de las listas originales
*this = temp;
// Esto evita que se destruyan los nodos de la lista temporal, que ahora es *this:
temp.primero = nullptr;
}
Al final, haremos que la lista actual *this, sea la lista temporal con la mezcla de todos los nodos, y para evitar que se destruyan los nodos contenidos en la lista temporal, (que son los mismos que contiene la lista *this), haremos que su puntero "primero" sea nulo.
Ejemplo completo
// ListaAb.h: Plantilla para lista abierta ordenada
// Incorpora un método para ordenar la lista usando el algoritmo de mezcla "merge sort"
// C con Clase. (C) Noviembre de 2025
// Plantilla para lista abierta
// Posibles mejoras:
// * Implementar constructor copia.
// * Implementar operador de asignación
// * Incorporar listas de inicialización
#ifndef _LISTAABIERTA_
#define _LISTAABIERTA_
template<class DATO>
class Lista {
private:
//// Clase local de Lista para Nodo de Lista:
template<class DATON>
class Nodo {
public:
// Constructor:
Nodo(const DATON dat, Nodo<DATON> *sig) : dato(dat), siguiente(sig) {}
// Miembros:
DATON dato;
Nodo<DATON> *siguiente;
};
int cuenta;
// Punteros de la lista, para cabeza y nodo actual:
Nodo<DATO> *primero;
Nodo<DATO> *actual;
Nodo<DATO> *ultimo;
// Método auxiliares para ordenar la lista
Lista<DATO> Separar(int);
void Mezclar(Lista<DATO> lista2);
void AgregarNodo(Nodo<DATO>* nodo);
public:
// Constructor y destructor básicos:
Lista() : cuenta(0), primero(nullptr), actual(nullptr), ultimo(nullptr) {}
~Lista();
// Funciones de inserción:
void InsertarFinal(const DATO dat);
void InsertarPrincipio(const DATO dat);
bool InsertarActual(const DATO dat);
void Insertar(const DATO dat);
// Funciones de borrado:
void BorrarActual();
bool BorrarPrimerValor(const DATO dat);
// Función de búsqueda:
bool BuscarPrimerValor(const DATO dat);
// Comprobar si la lista está vacía:
bool Vacia() { return primero==nullptr; }
// Devolver referencia al dato del nodo actual:
DATO &ValorActual() { return actual->dato; }
// Hacer que el nodo actual sea el primero:
void Primero() { actual = primero; }
// Comprobar si el nodo actual es válido:
bool Actual() { return actual != nullptr; }
// Moverse al siguiente nodo de la lista:
void Siguiente() { if(actual) actual = actual->siguiente; }
// Sobrecargar operator++ en forma sufija para los mismo:
void operator++(int) { Siguiente(); }
// Aplicar una función a cada elemento de la lista:
void ParaCada(void (*func)(DATO&));
// Devuelve el número de elementos en la lista:
int Cuenta() { return cuenta; }
// Ordena la lista usando el algoritmo "merge sort":
void OrdenarMezcla();
};
//////// Implementación:
// Destructor
template<class DATO>
Lista<DATO>::~Lista() {
while(!Vacia()) {
actual = primero;
primero = primero->siguiente;
delete actual;
}
}
template<class DATO>
void Lista<DATO>::InsertarFinal(const DATO dat) {
// Si la lista está vacía, insertar al principio:
if(Vacia()) InsertarPrincipio(dat);
else { // Si no lo está:
// Insertar a continuación del último elemento:
ultimo->siguiente = new Nodo<DATO>(dat, nullptr);
cuenta++;
ultimo = ultimo->siguiente;
}
}
template<class DATO>
void Lista<DATO>::InsertarPrincipio(const DATO dat) {
primero = new Nodo<DATO>(dat, primero);
if(primero->siguiente==nullptr) ultimo = primero;
cuenta++;
}
template<class DATO>
bool Lista<DATO>::InsertarActual(const DATO dat) {
// Sólo si la lista no está vacía y actual es válido:
if(!Vacia() && actual) {
actual->siguiente = new Nodo<DATO>(dat, actual->siguiente);
cuenta++;
if(actual==ultimo) ultimo = actual->siguiente;
return true;
}
// Si no se puede insertar, retornar con false:
return false;
}
// Insertar ordenadamente:
template<class DATO>
void Lista<DATO>::Insertar(const DATO dat) {
Nodo<DATO> *temp = primero;
Nodo<DATO> *anterior = nullptr;
// Si la lista está vacía, insertar al principio:
if(Vacia()) InsertarPrincipio(dat);
else {
// Buscar el nodo anterior al primer nodo con un dato mayor que 'dat'
while(temp && temp->dato < dat) {
anterior = temp;
temp = temp->siguiente;
}
// Si no hay anterior, insertar al principio,
// nuestro valor es el menor de la lista:
if(!anterior)
InsertarPrincipio(dat);
else {// Insertar:
anterior->siguiente = new Nodo<DATO>(dat, temp);
cuenta++;
if(temp==nullptr) ultimo = anterior->siguiente;
}
}
}
template<class DATO>
void Lista<DATO>::BorrarActual() {
Nodo<DATO> *anterior;
// Si el nodo actual es el primero:
if(actual && actual == primero) {
// El primer nodo será ahora el segundo:
// Sacar el nodo actual de la lista:
primero = actual->siguiente;
// Borrarlo:
delete actual;
actual = nullptr;
cuenta--;
if(primero==nullptr) ultimo = nullptr;
} else
if(actual && !Vacia()) {
// Buscar el nodo anterior al actual:
anterior = primero;
while(anterior && anterior->siguiente != actual)
anterior = anterior->siguiente;
// Sacar el nodo actual de la lista:
anterior->siguiente = actual->siguiente;
if(actual==ultimo) ultimo = anterior;
// Borrarlo:
delete actual;
actual = nullptr;
cuenta--;
}
}
// Borrar el primer nodo cuyo dato sea igual a 'dat':
template<class DATO>
bool Lista<DATO>::BorrarPrimerValor(const DATO dat) {
Nodo<DATO> *anterior = nullptr;
Nodo<DATO> *temp = primero;
if(!Vacia()) {
// Si la lista no está vacía, buscar el nodo a borrar (temp)
// y el nodo anterior a ese (anterior):
while(temp && temp->dato != dat) {
anterior = temp;
temp = temp->siguiente;
}
// Si el valor está en la lista:
if(temp) {
// Si anterior es válido, no es el primer valor de la lista
if(anterior) // Sacar nodo temp de la lista
anterior->siguiente = temp->siguiente;
else // Ahora el primero es el segundo:
primero = temp->siguiente; // Borrar primer elemento
if(temp==ultimo) ultimo = anterior;
// Borrar nodo:
delete temp;
cuenta--;
return true; // Se ha encontrado y borrado dat
}
}
return false; // valor no encontrado
}
// Busca el primer nodo con valor 'dat':
template<class DATO>
bool Lista<DATO>::BuscarPrimerValor(const DATO dat) {
actual = primero;
// Si la lista no está vacía:
if(!Vacia()) {
while(actual && actual->dato != dat) {
actual = actual->siguiente;
}
}
// Si el nodo es válido, se ha encontrado el valor:
return actual != nullptr;
}
// Aplicar una función a cada nodo de la lista:
template<class DATO>
void Lista<DATO>::ParaCada(void (*func)(DATO&)) {
Nodo<DATO> *temp = primero;
// Recorrer la lista:
while(temp) {
// Aplicar la función:
func(temp->dato);
temp = temp->siguiente;
}
}
// La función "func" debe ser una plantilla de una función
// que no retorne valor y que admita un parámetro del mismo
// tipo que la lista:
// template <class DATO>
// void <funcion>(DATO d);
// Divide la lista en dos. La primera es la propia lista, con n elementos,
// La segunda empieza en en el elemento n, hasta el final
template<class DATO>
Lista<DATO> Lista<DATO>::Separar(int n) {
Lista<DATO> retval;
if(n>cuenta) return retval;
Nodo<DATO> *temp = primero;
int i=0;
while(i++<n-1) temp = temp->siguiente;
retval.primero = temp->siguiente;
retval.cuenta = cuenta-n;
retval.ultimo = ultimo;
cuenta = n;
ultimo = temp;
temp->siguiente = nullptr;
return retval;
}
// Ordenar la lista mediante el algoritmo "merge sort"
template<class DATO>
void Lista<DATO>::OrdenarMezcla() {
if(cuenta<=1) return; // Una lista con cero o un elemento está ordenada
int n = cuenta/2; // Calcular el centro
Lista<DATO> lista2 = Separar(n);
OrdenarMezcla(); // Ordenar recursivamente la mitad izquierda
lista2.OrdenarMezcla(); // Ordenar recursivamente la mitad derecha
Mezclar(lista2); // Mezclar
lista2.primero=nullptr;
}
// Mezcla dos listas ordenadas *this y lista2, en la propia lista *this
template<class DATO>
void Lista<DATO>::Mezclar(Lista<DATO> lista2) {
// Necesitamos una lista temporal
Lista<DATO> temp;
// Mezclamos las dos sublistas *this y lista2
while(primero && lista2.primero) {
if(primero->dato <= lista2.primero->dato) {
temp.AgregarNodo(primero);
primero = primero->siguiente;
} else {
temp.AgregarNodo(lista2.primero);
lista2.primero = lista2.primero->siguiente;
}
}
// Copiar los elementos que quedan en la lista *this
while(primero) {
temp.AgregarNodo(primero);
primero = primero->siguiente;
}
// Copiar los elementos que quedn en la lista2
while(lista2.primero) {
temp.AgregarNodo(lista2.primero);
lista2.primero = lista2.primero->siguiente;
}
*this = temp;
temp.primero = nullptr;
}
// Agrega un nodo existente al final de la lista, sin modificarlo
template<class DATO>
void Lista<DATO>::AgregarNodo(Nodo<DATO>* nodo) {
if(ultimo) {
ultimo->siguiente=nodo;
ultimo = nodo;
} else {
primero = ultimo = nodo;
}
cuenta++;
}
#endif
Un programa de ejemplo para probar estas listas:
#include <iostream>
#include <string>
#include "lista.h"
void Mostrar(auto& d) {
std::cout << d << " ";
}
int main()
{
Lista<int> ListaInt;
// Inserción de algunos valores:
for(int i=0; i<25; i++) ListaInt.InsertarFinal(std::rand()%100);
ListaInt.ParaCada(Mostrar);
std::cout << std::endl;
ListaInt.OrdenarMezcla();
ListaInt.ParaCada(Mostrar);
std::cout << std::endl;
Lista<float> ListaFloat;
for(int i=0; i<11; i++) ListaFloat.InsertarFinal((std::rand()%10000)/100.0);
ListaFloat.OrdenarMezcla();
ListaFloat.ParaCada(Mostrar);
std::cout << std::endl;
Lista<char> ListaChar;
for(int i=0; i<11; i++) ListaChar.InsertarFinal((std::rand()%20)+'A');
ListaChar.OrdenarMezcla();
ListaChar.ParaCada(Mostrar);
std::cout << std::endl;
Lista<std::string> ListaString;
ListaString.InsertarFinal("Fernando");
ListaString.InsertarFinal("Alicia");
ListaString.InsertarFinal("Gabriel");
ListaString.InsertarFinal("Santiago");
ListaString.InsertarFinal("Ines");
ListaString.InsertarFinal("Eva");
ListaString.OrdenarMezcla();
ListaString.ParaCada(Mostrar);
std::cout << std::endl;
return 0;
}