Cuando abrimos un archivo de gran tamaño, lo dividimos en uno pequeño, lo ordenamos y luego lo fusionamos de nuevo en un gran archivo ordenado.fusión multidireccional vs fusión bidireccional
Al fusionar, podemos hacer muchos pases de combinación bidireccional o una combinación múltiple.
Me pregunto qué enfoque es mejor? ¿y por qué?
Una combinación de varias vías es generalmente mejor. Considere tres archivos pequeños:
a1
a2
a3
y
b1
b2
b3
y finalmente
c1
c2
c3
Si usted hace una fusión con a y b, nos quedamos con (digamos)
a1
b1
a2
b2
b3
a3
y
c1
c2
c3
Una fusión final sería crear la lista ordenada, notar cómo en esta última unión que tenemos para visitar las a y b artículos otra vez. Es esta re-fusión lo que es un desperdicio en las fusiones de dos vías en cascada.
Lo que puede hacer en su lugar es una única combinación de varias vías. Sin embargo, ten cuidado de cómo lo haces. Específicamente, evite el doble lazo ingenuo que escanea cada cursor para ver cuál tiene el valor mínimo. Use un min-heap en su lugar. Esto reducirá la complejidad a O(n log n).