l'unità di misura di questi algoritmi sono il numero di confronti. Se ci pensi bene il bubble fa O(n^2) confronti perchè va avanti finchè nn scambia + niente. Nel caso del merge il numero di confronti viene ad avere un ordine logaritmico moltiplicato per un fattore n. Intuitivamente n sta perchè la sequenza una volta la deve analizzare tutta, il logn invece (a grandi linee) viene fuori dalla profondità dell'albero della ricorsione che è appunto logaritmica (ogni nodo ha due figli etc..). Il fatto cruciale è che la procedura merge fonde due sequenze già ordinate, e quindi (riprendo dal libro dove ho studiato per l'esame) merge ci mette (l + m -1) confronti a fondere due sequenze già ordinate (dove l e m sono le lunghezze delle sequenze), e l +m -1 è ordine di n.
E' logico che se devi ordinare poche cose ti conviene un algoritmo tipo il selection sort, oppure meglio l'insertion sort, che sono entrambi a ordine di n^2, però meno stupidi del bubble!!
L'unico difettuccio del merge_sort è che la procedura merge ha bisogno di altra memoria ausialiare per fondere. Problema che il quick_sort se implementato in modo opportuno per partizionare in loco non ha.

Ciao ciao