Patrones de intercalación de varios pasos

PATRONES DE INTERCALACIÓN 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 meramente de estructurade datos, es la atención puesta en la enorme diferencia de costo entre el desplazamiento de disco y el acceso a la información en memoria RAM. Si el problema de intercalación implicara sólo operacionesen memoria RAM, la media importante de trabajo, o de costo, seria el número de comparaciones requeridas para terminar la intercalación. El patrón de intercalación que minimizaría l número decomparaciones en un problema de intercalar X porciones (Cada porción contiene un gran número de registros), sería la intercalación de X formas por intercalación múltiple. Si se concidera desde un punto devista que ignore el costo de los desplazamientos, esta intercalación de k formas tiene las características:  Cada registro se lee sólo una vez  Si se usa un árbol de selección para las comparacionesefectuadas en la operación de intercalación, entonces el número de comparaciones requeridas para una intercalación de k formas de N registros (totales) es función de N x log K.  Puesto que k esdirectamente proporcional a N , ésta es una operación o(NxlogN), la cual es razonablemente eficiente aún cuando N crezca mucho. Todo esto seria muy bueno si se tratara exclusivamente de memoria RAM, pero elverdadero propósito de este procedimiento de clasificación por intercalación es poder clasificar archivos que son demasiado grandes para caber en la memoria RAM. Para el caso por resolver, los costosasociados con los desplazamientos en el disco son órdenes de magnitud mayores que los costos de las operaciones en memoria RAM. En consecuencia, si pueden sacrificarse las ventajas de intercalación deX formas y cambiarlas por ahorro de tiempo de desplazamientos, puede obtenerse una ganancia neta en el desempeño. Si X fuese igual a 40. En vez de intercalar 40 porciones a la vez, se podrían...