RE:ordenmaiento por mezcla
En informática, tipo de combinación o mergesort es un algoritmo de ordenación para la reordenación de las listas (o cualquier otra estructura de datos que sólo se puede acceder de forma secuencial, por ejemplo, secuencias de archivo) en un orden especificado. Es un ejemplo particularmente bueno de la divide y vencerás paradigma algorítmico. Es una especie de comparación.
Conceptualmente, la combinación de obras tipo de la siguiente manera:
1.Divide la lista sin ordenar en dos sublistas de la mitad del tamaño
2.Sort cada uno de los dos sublistas
3.Merge los dos sublistas, ordenados de nuevo en una lista ordenada.
El algoritmo fue inventado por John von Neumann en 1945.
El código siguiente muestra cómo implementar la fusión de ordenación en Java.
public static void mergeSort( Comparable [ ] a ) {
Comparable [ ] tmpArray = new Comparable[ a.length ];
mergeSort( a, tmpArray, 0, a.length - 1 );
}
private static void mergeSort( Comparable [ ] a, Comparable [ ] tmpArray,
int left, int right ) {
if( left < right ) {
int center = ( left + right ) / 2;
mergeSort( a, tmpArray, left, center );
mergeSort( a, tmpArray, center + 1, right );
merge( a, tmpArray, left, center + 1, right );
}
}
private static void merge( Comparable [ ] a, Comparable [ ] tmpArray,
int leftPos, int rightPos, int rightEnd ) {
int leftEnd = rightPos - 1;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos + 1;
// Main loop
while( leftPos <= leftEnd && rightPos <= rightEnd )
if( a[ leftPos ].compareTo( a[ rightPos ] ) <= 0 )
tmpArray[ tmpPos++ ] = a[ leftPos++ ];
else
tmpArray[ tmpPos++ ] = a[ rightPos++ ];
while( leftPos <= leftEnd ) // Copy rest of first half
tmpArray[ tmpPos++ ] = a[ leftPos++ ];
while( rightPos <= rightEnd ) // Copy rest of right half
tmpArray[ tmpPos++ ] = a[ rightPos++ ];
// Copy tmpArray back
for( int i = 0; i < numElements; i++, rightEnd-- )
a[ rightEnd ] = tmpArray[ rightEnd ];
}
