Me gustaría implementar mi propia ordenación por fusión (merge sort) de listas. Sé cómo hacerlo con arrays y vectores, pero he de usar la librería estándar de C++ de list. En http://www.cplusplus.com/reference/stl/list/ no he sabido encontrarlo.
Si implemento mi propia lista, con nodos y punteros al siguiente sé cómo hacerlo, pero no sé cómo funciona en la librería de C++.
Código: Seleccionar todo
list<my_clase> fusionar(list<my_clase> L1, list<my_clase> L2) {
if (L1.empty()) return L2;
if (L2.empty()) return L1;
list<my_clase>::iterator it1 = L1.begin();
list<my_clase>::iterator it2 = L2.begin();
if (*it1 <= *it2) {
L1 -> siguiente = fusionar(L1 -> siguiente, L2)
return L1;
};
else {
L2 -> siguiente = fusionar(L1, L2 -> siguiente);
return L2;
}
}
void dividir(list<my_clase>& L1, list<my_clase>& L2, int m){
list<my_clase>::iterator it = L1.begin();
while (m > 1) {
++it;
--m;
};
L2 = it "-> siguiente", para que nos entendamos.
it "-> siguiente" = NULL;
}
void mergesort (list<my_clase>& lista, int n) {
if (n <= 1) return;
int m = n / 2;
list<my_clase> aux = NULL;
dividir(lista, aux, m);
mergesort(L, m);
mergesort(aux, n - m);
lista = fusionar(lista, aux);
}