Patrones de intercalacion

PATRONES DE INTERCALACION DE VARIOS PASOS

Uno de los rasgos distintivos de la solución a un problema de estructuras de archivos, en contraste con la solución de un problema meramentede estructura de datos, es la atención puesta en la enorme diferencia de costos entre el desplazamiento en disco y le acceso a la información en memoria RAM. Si el problema deintercalación implicara solo operaciones en
memoria RAM, la medida importante de trabajo, o de costo, sería el numero de comparaciones requeridas para terminar la intercalación. El patrón deintercalación que minimiza el numero de comparaciones en el problema del ejemplo, en el que se pretenden intercalar 40 porciones, seria la intercalación de 40 formas estudiada en la secciónanterior. Si se considera desde un punto de vista que ignore el costo de los desplazamientos, esta intercalación de K formas
Tiene las siguientes características deseables:

PROCESAMIENTOSECUENCIAL COORDINADO....
* Cada registro se lee solo una vez
* Si se usa un árbol de selección para las comparaciones efectuadas en la operación de intercalación, como se describe en lasección 8.3, entonces el numero de comparaciones requeridas para una intercalación de K formas de N registros (totales)es función de:

N * logK

* Puesto que K es directamente proporcional a N, esta es una operación O(N*log N) (medida en numero de comparaciones), la cual es razonablemente eficiente aun cuando N crezca mucho.Todo esto seria bueno si se trabajara exclusivamente en memoria RAM, pero el verdadero propósito de este procedimiento de clasificación por intercalación es poder clasificar archivos que sondemasiado grandes para caber en la memoria RAM.
Para el caso por resolver, los costos asociados con el desplazamiento en el disco son órdenes de magnitud mayores que los costos de las operaciones en...