R1 R2 R3 Ri Rn
........------------------.......--------.......--------.......
| K1 | K2 | K3 | | Ki | | Kn | n slots Archivo original
........------------------.......--------.......--------.......
R1 R2 R3 Ri Rn
........------------------.......--------.......--------.......
| K1 | K2 | K3 | | Ki | | Kn | n slots Archivo de trabajo
........------------------.......--------.......--------.......
En el ejemplo pueden observarse como evolucionan los subarchivos de
registros ordenados, subarchivos que están cerrados entre corchetes.
Paso R1 R2 R3 R4 R5 R6 R7 R8 R9 R10
1 [ 26 ] [ 5 ] [ 77 ] [ 1 ] [ 61 ] [ 11 ] [ 59 ] [ 15 ] [ 48 ] [ 19 ]
2 [ 5 26 ] [ 1 77 ] [ 11 61 ] [ 15 59 ] [ 19 48 ]
3 [ 1 5 26 77 ] [ 11 15 59 61 ] [ 19 48 ]
4 [ 1 5 11 15 26 59 61 77 ] [ 19 48 ]
5 [ 1 5 11 15 19 26 48 59 61 77 ]
Necesitamos contar con una funcion elemental de mezcla, la cual
utilizaremos reiteradamente.
Esta funcion devuelve un archivo ordenado, si recibe dos subarchivos ordenados.
Los subarchivos ordenados van desde los indices xl a xm el primero y
desde xm+1 a xn el segundo.
El archivo final ordenado va de xl a xn y ocupa un espacio adicional igual
al espacio que ocupan los dos archivos originales.
Xl Xl+1 Xl+2 Xm Xm+1 Xm+2 Xn-2 Xn-1 Xn
........------------------.......------------------.......------------------.......
| | | | | | | | | | | | n slots Archivo original
........------------------.......------------------.......------------------.......
|.............. i ...........>|............... j ...............>|
|--- Subarchivo ordenado 1 -->|------ Subarchivo ordenado 2 ---->|
Zl Zl+1 Zl+2 Zm Zm+1 Zm+2 Zn-2 Zn-1 Zn
........------------------.......------------------.......------------------.......
| | | | | | | | | | | | n slots Archivo mezclado
........------------------.......------------------.......------------------.......
|............................... k .............................>|
|<----------------- Archivo ordenado mezclado ------------------>|
Las claves de cada registro se denota con misma letra que los registros, pero
en minúscula. Por ejemplo, la clave del registro Xm es xm.
Donde :
k <---- k + 1
Observar que los dos subarchivos originales ordenados deben estar contiguos en memoria.
Observar que el while controla que se procese solo dentro de los margenes de los dos subarchivos ordenados originales.
Observar que en la transferencia del remanente del subarchivo no agotado a la salida uso una notacion abreviada,
en realidad se necesitaria de un loop para dicha transferencia.
Observar que no es necesario que los subarchivos ordenados sean del mismo ancho, pudiendo ser de cualquier ancho, como muestra la siguiente figura.
|................... i ................>|...... j .......>|
........-------------------------------------------------------------.......
| | ........................... | | | ..... | |
........-------------------------------------------------------------.......
l m m+1 n
Esta funcion intermedia sera utilizada repetidamente y administra los pasos
requeridos para clasificar un archivo. Como puede apreciarse en el ejemplo 1 :
Puede apreciarse tambien, que el ultimo subarchivo puede ser de ancho menor a los precedentes.
<---------- 2a --------->
........------------------------------------------------------------------............
| a | a | a | a | a | h |
........------------------------------------------------------------------............
1 2a+1 4a+1 h = n - ( 2*a ) - 1
|............................... i ..............................>
Donde :
Veamos la funcion final, la cual invoca a la intermedia y esta a la elemental.
Observar que el archivo de trabajo y el archivo original intercambian sus roles en el algoritmo.
X1 Xn
*--*--.................................................--*--*
| | | |
*--*--.................................................--*--*
Y1 Yn
*--*--.................................................--*--*
| | | |
*--*--.................................................--*--*
Donde :
Observar que para clasificar un archivo desordenado de n registros
se deben hacer i pasos, siendo i el techo de log2 n.
Teniendo en cuenta que los ordenes de magnitud de los siguientes metodos de
clasificacion son :
La pregunta que surge es : ¨ Cuan rapido puedo clasificar ?.
Tener en cuenta que la mejora en el orden de magnitud por clasificar
con el Merge Sort acarrea un costo de almacenamiento, que es el doble
del uso de memoria del Insert Sort.