1. Dividir la lista:
- Si la lista contiene uno o cero nodos, se considera ya ordenada.
- En caso contrario, divida la lista en dos mitades aproximadamente iguales.
2. Conquistar (ordenar las sublistas):
- Aplique recursivamente el algoritmo de clasificación por combinación a ambas mitades de la lista, clasificándolas de manera efectiva.
3. Fusionar las sublistas ordenadas:
- Comience con dos punteros, uno apuntando al encabezado de cada sublista ordenada.
- Compare los datos en los nodos señalados por estos punteros para determinar qué elemento aparece primero en el orden de clasificación.
- Agregar el elemento más pequeño a una nueva lista que se está construyendo.
- Mueve el puntero correspondiente al siguiente nodo de la sublista.
4. Repita el paso 3:
- Continúe comparando y fusionando elementos de ambas sublistas, moviendo punteros según sea necesario.
- Repita este proceso hasta que todos los elementos de ambas sublistas se hayan fusionado en la nueva lista.
5. Devuelve la lista ordenada fusionada:
- Una vez que se han fusionado todos los elementos, la nueva lista resultante representa la lista enlazada ordenada. Devuelve esta lista ordenada como respuesta final.
Al dividir sistemáticamente la lista en partes más pequeñas, ordenarlas y fusionarlas nuevamente, la ordenación por fusión clasifica efectivamente toda la lista vinculada en orden ascendente. La complejidad temporal de este enfoque es O (n log n), donde n es el número de nodos en la lista vinculada.