tecno

Ordenamiento por Mezcla
 Editar 0 1…
Merge Sort (Ordenamiento por mezcla) 
Esta basado en la técnica de “divide y venceras “. Primero toma el arreglo original de datos,lo divide en dos partes del mismo tamaño cada una, y lo sigue dividiendo hasta que solo quede un elemento. Cada una de las divisiones se ordena de manera separada y luegose unen para formar el arreglo ya ordenado. Este algoritmo divide inicialmente la lista hasta su mínimo valor y luego ordena el arreglo. 
Orden de Complejidad: Es de ordenO(nlog(n)), esta crece mas rápidamente que la función n. 
Pseudocodigo del metodo 
Public void mergesort {int a []}
{ mergesort { a, 0, a.lenght -1 ); 
} 
Int len,pivote, m1, m2; 
If {bajo == alto }
{ return;}
Else
{ len = alto – bajo +1;
Pivote = { bajo + alto} /2;
Mergesort { a, bajo, pivote};
Mergesort{ a, pivote+1, alto} 
Inttemp[] = new int (len); 
For (int i=0; I < len; i++) 
{ 
If (m2 1) 
{ 
n1 = n / 2; 
n2 = n - n1; 
mergesort(matrix, init, n1); 
mergesort(matrix, init + n1, n2); merge(matrix, init, n1, n2); 
} 
} 

Y el algoritmo que nos permite mezclar los elementos según corresponda: 

private static void merge(int[ ] matrix, int init, intn1, int n2) 
{ 
int[ ] buffer = new int[n1+n2]; 
int temp = 0; 
int temp1 = 0; 
int temp2 = 0; 
int i; 
while ((temp1 < n1) && (temp2 < n2)) 
{ 
if (matrix[init +temp1] < matrix[init + n1 + temp2]) 
buffer[temp++] = matrix[init + (temp1++)]; 
else 
buffer[temp++] = matrix[init + n1 + (temp2++)]; 
} 
while (temp1 < n1) buffer[temp++] = matrix[init + (temp1++)]; 
while (temp2 < n2) 
buffer[temp++] = matrix[init + n1 + (temp2++)]; 
for (i = 0; i < n1+n2; i++) 
matrix[init + i] = buffer[i]; 
}