Fue desarrollado en 1945 por John Von Neumann.

A grandes rasgos, el algoritmo consiste en dividir en dos partes iguales el vector a ordenar,
ordenar por separado cada una de las partes, y luego mezclar ambas partes, manteniendo el orden, en un solo vector ordenado.

Fuente:Fuente: wikipedia
A continuación se describe el algoritmo

public static void mezclaorden( Comparable [ ] comp ) {
Comparable [ ] tmpArray = new Comparable[ comp.length ];
mezclaorden( comp, tmpArray, 0, comp.length – 1 );
}

private static void mezclaorden( Comparable [ ] comp, Comparable [ ] tmpArray,
int der, int izq ) {
if( izq < der ) {
int center = ( izq + der ) / 2;
mezclaorden( comp, tmpArray, izq, center );
mezclaorden( comp, tmpArray, center + 1, der );
mezclar( comp, tmpArray, izq, center + 1, der );
}
}

private static void mezclar( Comparable [ ] comp, Comparable [ ] tmpArray,
int PosIz, int PosDer, int findere) {
int finizq = PosDer – 1;
int tmpPos = PosIz;
int cant = findere – PosIz + 1;

while( PosIz <= finizq && PosDer <= findere )
if( comp[ PosIz ].compareTo( comp[ PosDer ] ) <= 0 )
tmpArray[ tmpPos++ ] = comp[ PosIz++ ];
else
tmpArray[ tmpPos++ ] = comp[ PosDer++ ];

while( PosIz <= finizq )
tmpArray[ tmpPos++ ] = comp[ PosIz++ ];

while( PosDer <= findere )
tmpArray[ tmpPos++ ] = comp[ PosDer++ ];

for( int i = 0; i < cant; i++, findere– )
comp[ findere ] = tmpArray[ findere ];
}