Fusione
Di sottosequenze
Supponiamo che l'array v contenga due sottoarray adiacenti ordinati
- v', da inf a medio
- v'', da medio+1 a sup
e che l'obbiettivo sia ordinare l'array da inf a sup.
Esempio 1
Siano
v = (1, 2, 4, 5, 7, 10, 2, 3, 4, 6), inf=0, medio=5, sup=9
allora
v' = (1, 2, 4, 5, 7, 10), v'' = (2, 3, 4, 6) --> v = (1, 2, 2, 3, 4, 4, 5, 6, 7, 10)
Esempio 2
Siano
v = (1, 2, 4, 5, 7, 10, 2, 3, 4, 6), inf=4, medio=5, sup=7
allora
v' = (7, 10), v'' = (2, 3), v = (1, 2, 4, 5, 2, 3, 7, 10, 4, 6)
Si puņ adattare l'algoritmo di fusione in modo che i dati siano copiati, in ordine, su un array temporaneo e poi ricopiati su v, da inf a sup.
Pseudocodice
PROCEDURA merge(IN/OUT REALE v[], IN INTERO inf, IN INTERO medio, IN INTERO sup)
INIZIO
INTERO i1=inf,
i2=medio+1,
i3=0,
n3=sup-inf+1
REALE v3[]=NUOVO REALE[n3]
MENTRE(i1 <= medio AND i2 <= sup)
INIZIO
SE(v[i1] <= v[i2]) ALLORA
INIZIO
v3[i3]=v[i1]
i1=i1+1
FINE
ALTRIMENTI
INIZIO
v3[i3]=v[i2]
i2=i2+1
FINE
i3=i3+1
FINE
MENTRE(i1 <= medio)
INIZIO
v3[i3]=v[i1]
i1=i1+1
i3=i3+1
FINE
MENTRE(i2 <= sup)
INIZIO
v3[i3]=v[i2]
i2=i2+1
i3=i3+1
FINE
PER(i1 DA inf A sup PASSO +1)
v[i1]=v3[i1-inf]
FINE
INIZIO
INTERO i1=inf,
i2=medio+1,
i3=0,
n3=sup-inf+1
REALE v3[]=NUOVO REALE[n3]
MENTRE(i1 <= medio AND i2 <= sup)
INIZIO
SE(v[i1] <= v[i2]) ALLORA
INIZIO
v3[i3]=v[i1]
i1=i1+1
FINE
ALTRIMENTI
INIZIO
v3[i3]=v[i2]
i2=i2+1
FINE
i3=i3+1
FINE
MENTRE(i1 <= medio)
INIZIO
v3[i3]=v[i1]
i1=i1+1
i3=i3+1
FINE
MENTRE(i2 <= sup)
INIZIO
v3[i3]=v[i2]
i2=i2+1
i3=i3+1
FINE
PER(i1 DA inf A sup PASSO +1)
v[i1]=v3[i1-inf]
FINE
