## 2.1.2 ORDENAMIENTO POR MEZCLA

En el Ordenamiento por Mezcla (merge sort) se aplica la técnica divide y vencerás, dividiendo la secuencia de datos en dos subsecuencias hasta que las subsecuencias tengan un único elemento, luego se ordenan mezclando dos subsecuencias ordenadas en una secuencia ordenada, en forma sucesiva hasta obtener una secuencia única ya ordenada.

Si n = 1 solo hay un elemento por ordenar, sino se hace una ordenación de mezcla de la primera mitad del arreglo con la segunda mitad. Las dos mitades se ordenan de igual forma.

Ejemplo: Se tiene un arreglo de 8 elementos, se ordenan los 4 elementos de cada arreglo y luego se mezclan. El arreglo de 4 elementos, se ordenan los 2 elementos de cada arreglo y luego se mezclan. El arreglo de 2 elementos, como cada arreglo sólo tiene n = 1 elemento, solo se mezclan.

void ordenarMezcla(TipoEle A[], int izq, int der)
{ if ( izq < der )
{ centro = ( izq + der ) % 2;
ordenarMezcla( A, izq, centro );
ordenarMezcla( A, centro+1, der);
intercalar( A, izq, centro, der );
}
}
void intercalar(TipoEle A[], int a, int c, int b )
{ k = 0;
i = a;
j = c + 1;
n = b - a;
while ( i < c + 1 ) && ( j < b + 1 )
{ if ( A[i] < A[j] )
{ B[k] = A[i];
i = i + 1;
}
else
{ B[k] = A[j];
j = j + 1;
}
k = k + 1;
};
while ( i < c + 1 )
{ B[k] = A[i];i++;
k++;
};
while ( j < b + 1 )
{ B[k] = A[j];
j++;
k++;
};
i = a;
for ( k = 0; k < n; i++ )
{ A[i] = B[k];
i++;
};
};

Análisis del algoritmo: La relación de recurrencia del algoritmo es T(1) = 1, T(n) = 2 T(n/2) + n, cuya solución es T(n) = n log n.

###