Page 23 - REVISTA MATINF Nr. 5

Complexitatea algoritmului de sortare prin interclasare (mergesort) 23

Totus , i, conform Corolarului 1 din [3], algoritmul de sortare prin interclasare nu este
optim, nici ˆın raport cu timpul mediu de execut , ie, deoarece arborele extins de sortare
asociat nu are ˆıntotdeauna toate nodurile externe situate doar pe ultimul s , i, eventual, pe
penultimul nivel, nici ˆın raport cu timpul de execut , ie ˆın cazul cel mai defavorabil,
deoarece ˆın˘alt , imea acestui arbore nu este ˆıntotdeauna egal˘a cu dlog n!e. De exemplu, pentru
2
n = 5 exist˘a noduri externe nesituate pe acelas , i nivel sau pe dou˘a nivele consecutive, iar
ˆın˘alt , imea arborele extins de sortare asociat este mai mare decˆat dlog 5!e = dlog 120e = 7, as , a
2 2
cum reiese din figura urm˘atoare, ˆın care este reprezentat˘a doar o parte a arborelui extins de
sortare.

1?2

≤

1?3
≤

2?3
≤

4?5

≤

1?4
≤ >

2?4 1?5
≤ ≤ >

3?4 2?5 (4,5,1,2,3)

≤ ≤
(1,2,3,4,5) 3?5

≤ >

(4,1,2,3,5) (4,1,2,5,3)

Observat ,ia 4. O alt˘a justificare a neoptimalit˘at , ii (pure a) algoritmului de sortare prin interclasare
este urm˘atoarea: ˆın cazul cel mai defavorabil la sortarea unui vector cu n componente, num˘arul
de comparat ,ii de chei efectuate de algoritmul mergesort este, conform (10),

+
N (n) = dlog 1e + dlog 2e + . . . + dlog ne,
c 2 2 2
iar num˘arul de comparat ,ii de chei efectuate de orice algoritm optim este, conform Corolarului 1
din [3],
N def (n) = dlog n!e = dlog 1 + log 2 + . . . + log ne.
2
2
2
2
Evident, pentru orice numere reale x s , i y avem
dxe + dye ≥ dx + ye (19)