Originariamente inviato da conqueror
a questo punto entra in atto una procedura chiamata "merge" che fonde le varie sottosequenze (a coppie) tenendo conto dell'ordinamento.
Quindi:

[2 14] [5 9] [1 20]

poi

[2 5 9 14] [1 20]

poi

[1 2 5 9 14 20]

Non per niente la procedura merge è la parte + complicata dell'intero merge_sort che altrimenti si ridurrebbe a un pò di chiamate ricorsive.

Invece il quick_sort è un algoritmo che nel caso medio ha un costo che è O(nlog(n)) che teoricamente è + veloce del merge sort andando a guardare le costanti che la notazione O si mangia. Però se nella scelta del pivot si va beccare proprio il mediano risulta che ha un costo di n^2, per questo lo si rende probabilistico (randomizzato) il quick_sort. Il quick sort si usa di + perchè è anche di + facile implementazione.

Ciao ciao
ah ecco...ma questa cosa riduce davvero il tempo rispetto al bubble sort? A me sembra che si mangia una sacco di processore e di memoria...La ricorsione è costosa...
Capisco che il bubble sort nel caso peggiore è qualcosa come n! o n^2, però è un for semplice semplice