MergeSort

Questa lezione ha come oggetto l'algoritmo di ordinamento MergeSort.

1. Leggere lo pseudocodice seguente. Si noti che il codice funziona per vettori con primo indice pari a 1 (e non 0). Riadattare il codice oppure usarlo su vettori dall'indice 1 in avanti.

   Merge(A, p, q, r)
   n1 = q-p+1
   n2 = r-q
   FOR (i=1 to n1)
     L[i] = A[p+i-1]
   ENDFOR
   FOR (j=1 to n2)
     R[j] = A[q+j]
   ENDFOR
   L[n1 + 1] = inf
   R[n2 + 1] = inf
   i = 1
   j = 1
   FOR (k=p to r)
     IF (L[i] <= R[j])
       A[k] = L[i]
       i = i+1
     ELSE
       A[k] = R[j]
       j = j+1
     ENDIF
   ENDFOR
   
   
   MergeSort(A, p, r)
   IF (p < r)
     q = (p+r) div 2 
     MergeSort(A, p, q)
     MergeSort(A, q+1, r)
     Merge(A, p, q, r)
   ENDIF
   
   
   

2. Scrivere una classe MergeSort che ordina, in senso crescente, un vettore casuale di interi con il metodo do ordinamento MergeSort.
3. Aggiornare la classe SortWorkBench con l'algoritmo MergeSort. Fare in modo che la classe scriva le statistiche calcolate (media e coefficiente di variazione) per i vari algoritmi di ordinamento in una tabella di un documento HTML. Visualizzare quindi il documento con un browser. Per scrivere su un file in Java usare la classe PrintWriter come segue:

   PrintWriter html = null;
   try {
     html = new PrintWriter("sortBenchmark.html");
   } catch (IOException ioe) {ioe.printStackTrace();}
   html.println("...");
   html.close();