Page 15 - REVISTA MATINF Nr. 5

˘
ARTICOLE SI NOTE DE INFORMATICA
,

Complexitatea algoritmului de sortare prin interclasare
(mergesort)

Costel B˘alc˘au 1

Algoritmul de sortare prin interclasare (mergesort), inventat de c˘atre faimosul savant John
von Neumann ˆın anul 1945, este unul dintre cei mai performant , i algoritmi de sortare.
ˆ
In articolul de fat , ˘a vom analiza riguros complexitatea acestui algoritm, utilizˆand rezultate
de baz˘a din teoria algoritmilor privind ordinele de complexitate s , i arborii de sortare prezentate
ˆın [2], [3], precum s , i tehnici matematice de rezolvare a relat , iilor de recurent , ˘a.

Astfel vom putea studia eficient , a s , i optimalitatea acestui algoritmˆın cadrul clasei algoritmilor
de sortare bazat , i pe comparat , ii de chei.

Descrierea algoritmului

Pentru a sorta cresc˘ator un vector dat A = (a 1 , a 2 , . . . , a n ), n ≥ 1, algoritmul de sortare
prin interclasare (mergesort) utilizeaz˘a urm˘atorul procedeu specific metodei de programare
Divide et Impera:

• Dac˘a n = 1, atunci vectorul este deja sortat (avˆand un singur element);

• Dac˘a n ≥ 2, atunci:

– Se ˆımparte vectorul A ˆın doi subvectori

n + 1 l m
› ž
n
(a 1 , . . . , a m ) s , i (a m+1 , . . . , a n ) , unde m = =
2 2
(deci a m este elementul median s , i cei doi subvectori au dimensiuni cˆat mai apropiate
posibil);

– Se sorteaz˘a cresc˘ator cei doi subvectori, prin acelas , i procedeu;
– Se interclaseaz˘a cei doi subvectori sortat , i, adic˘a se reconstruies , te vectorul A astfel
ˆıncˆat s˘a cont , in˘a toate componentele celor doi subvectori sortat , i (deci toate cele n
componente ale vectorului init , ial) s , i care s˘a fie, de asemenea, sortat cresc˘ator.

Reamintim c˘a bxc reprezint˘a partea ˆıntreag˘a (inferioar˘a) a num˘arului real x (adic˘a aproximarea
ˆıntreag˘a prin lips˘a a lui x, notat˘a de obicei cu [x]), iar dxe reprezint˘a partea ˆıntreag˘a superioar˘a
a num˘arului real x (adic˘a aproximarea ˆıntreag˘a prin adaos a lui x).
1
Conf. univ. dr., Universitatea din Pites , ti, cbalcau@yahoo.com

15