Clasificacion por mezclas
Llohanna Alonso
David Blanco
Martil Gaitan
El método de clasificación por mezcla resulta apropiado cuando la colección de elementos a clasificar está representada mediante una lista enlazada, y no lo es tanto para una lista con representación contigua por la cantidad de espacio que necesitaría. El método usa la técnica divide y vencerás de la siguiente forma.Si la lista está constituida por un único elemento o es vacía, entonces está ya clasificada. En caso contrario, se divide la lista en dos sublistas de igual tamaño y se clasifican ambas (la recursividad resulta entonces idónea para ordenar ambas sublistas). Finalmente, las dos sublistas clasificadas se mezclan en una única, que será la lista original clasificada. El tiempo de ejecución requerido por el método es O(nlogn) (tanto en el caso promedio como en el peor caso), y es debido a que es posible mezclar dos listas clasificadas para obtener una única lista también clasificada en un tiempo de ejecución O(n).Ya que la división de una lista en dos sublistas del mismo tamaño se puede hacer también en un tiempo de ejecución O(n), y el árbol de expansión de la recursividad es de profundidad logn al tratarse de un árbol binario balanceado, el tiempo de ejecución total del algoritmo es de O(nlogn) (el cálculo del tiempo de ejecución del algoritmo para los casos peor y promedio es equivalente al cálculo del tiempo de ejecución del algoritmo quicksort para el caso promedio).
