LabASD - Merge sort

Nicolas Farabegoli nicolas.farabegoli2@unibo.it

Moreno Marzolla moreno.marzolla@unibo.it

Ultimo aggiornamento: 2021-03-18

Implementare l'algoritmo Merge sort in modo tale che i test forniti passino correttamente. Merge sort è stato ideato da John Von Neumann nel 1945.

Figura 1: John von Neumann By LANL - http://www.lanl.gov/history/atomicbomb/images/NeumannL.GIF (archive copy), Attribution, >https://commons.wikimedia.org/w/index.php?curid=3429594>
Figura 1: John von Neumann By LANL - http://www.lanl.gov/history/atomicbomb/images/NeumannL.GIF (archive copy), Attribution, >https://commons.wikimedia.org/w/index.php?curid=3429594>

L'algoritmo Merge Sort basa il suo funzionamento sul paradigma divide et impera. L'array da ordinare viene suddiviso in due metà che sono ordinate ricorsivamente. Fatto questo, le due metà vengono ricomposte mediante una procedura merge(). Si faccia riferimento alla Figura 1 per un esempio.

Figura 1: Merge Sort
Figura 1: Merge Sort

Nell'algoritmo Merge Sort la fase divide è semplice, mentre la fase impera (fusione di due array ordinati) è più laboriosa da realizzare.

Detto \(T(n)\) il tempo necessario ad ordinare un array di lungehzza \(n\) usando Merge Sort, possiamo definire \(T(n)\) in modo ricorsivo come segue:

\[ T(n) = \begin{cases} c_1 & \mbox{se } n \leq 1 \\ 2T(n/2) + c_2 n & \mbox{altrimenti} \end{cases} \]

dove \(c_1\) e \(c_2\) sono opportune costanti. La componente \(c_2 n\) indica il tempo necessario alla fase di fusione (merge), che è appunto proporzionale alla somma delle dimensioni delle metà da fondere. Applicando il Master Theorem si ha \(T(n) = \Theta(n \log n)\).

In questo programma viene proposta la versione ricorsiva; chi lo desidera può realizzare la versione iterativa di MergeSort.

Suggerimenti

La funzione merge() richiede un buffer di memoria temporaneo per effettuare la fusione dei sottovettori ordinati. È possibile allocare e deallocare buffer temporanei all'interno della funzione, ma questo sarebbe molto inefficiente.

Nel codice fornito, la funzione merge_sort() alloca un buffer temporaneo di lunghezza \(n\) e passa tale buffer alle funzioni di supporto merge_sort_rec() e merge(). Queste ultime possono usare liberamente tale buffer, quando necessario, eliminando l'overhead che sarebbe causato dalle ripetute chiamate a malloc() e free().

Per approfondire

Questo programma misura in modo grossolano il tempo necessario a ordinare l'array. Considerando array di dimensioni sufficientemente grandi (es., 100000 elementi o più), come varia il tempo di esecuzione nei seguenti casi? (dalla teoria dovreste già conoscere la risposta)

Per eseguire le prove di cui sopra occorre modificare opportunamente la funzione main() per generare degli array di input opportuni. Nel caso possano risultare utili, vengono fornite due funzioni randab() e random_shuffle(), la cui specifica è indicata nei commenti al codice.

File