Soluzione 7.7

Leggere con attenzione i commenti al codice del metodo iterativeMergeSort. Provare a verificarne "a mano" il comportamento su un array di prova.
Notare inoltre che il metodo iterativeMergeSort lavora su oggetti di tipo Comparable.
import java.util.Scanner;

public class IterMergeSortTester
{
    public static void main(String[] args)
    {
        System.out.println(
                  "Inserisci numeri double (Enter e < CTRL >+d per concludere)");
        Double[] v = readDoubleArray();
        iterativeMergeSort(v);
        System.out.println("\nNumeri ordinati con mergeSort iterativo:");
        for (int i = 0; i < v.length; i++)
            System.out.println(v[i]);
    }

    private static Double[] readDoubleArray()
    {
        Scanner in = new Scanner(System.in);
        Double[] v = new Double[1];
        int vSize = 0;
        while (in.hasNextLine())
        {
            String line = in.nextLine();
            Scanner linescan = new Scanner(line);
            while (linescan.hasNext())
            {
                if (vSize == v.length)
                {   //facciamo un resize senza scrivere un metodo ausiliario...
                    Double[] v2 = new Double[vSize*2];
                    System.arraycopy(v, 0, v2, 0, vSize);
                    v = v2;
                }
                v[vSize++] = Double.parseDouble(linescan.next());
            }
        }
        if (vSize != v.length)
        {
            Double[] v2 = new Double[vSize]; // usiamo un array pieno
            System.arraycopy(v, 0, v2, 0, vSize);
            v = v2;
        }
        return v;
    }

    private static void iterativeMergeSort(Comparable[] v)
    {
        /*
          ad ogni passo di iterazione, dim e` la dimensione di tutti i 
          sottoarray da esaminare. Attenzione all'aggiornamento di dim nel ciclo
        */
        for (int dim = 1; dim < v.length; dim *= 2) 
        {
            int begin1 = 0;             //inizio primo sotto-array da fondere
            int begin2 = begin1 + dim;  //inizio secondo sotto-array da fondere
            while (begin2 + dim <= v.length)
            {
                Comparable[] v1 = new Comparable[dim];
                Comparable[] v2 = new Comparable[dim];
                System.arraycopy(v, begin1, v1, 0, dim);
                System.arraycopy(v, begin2, v2, 0, dim);
                Comparable[] v3 = new Comparable[dim*2];
                merge(v3, v1, v2);
                System.arraycopy(v3, 0, v, begin1, dim*2);
                begin1 = begin2 + dim;  //passa ai due sottoarray successivi
                begin2 = begin1 + dim;
            }
            /*
             Cosa succede se la dimensione dell'array non e' una potenza di 2?
             Effettuare qualche prova a mano e verificare che all'ultima 
             iterazione del ciclo esterno il codice sopra scritto omette di 
             elaborare la parte terminale dell'array (provare ad esempio con
             dimensioni n = 9...15 e osservare cosa succede agli ultimi elementi 
             dell'array).
             Il codice che segue gestisce questo eventuale "frammento terminale"
             e rende il metodo funzionante anche quando la dimensione dell'array
             non e` una potenza di 2
            */
            if (begin2 < v.length)//caso in cui il secondo sottoarray della 
            {                     //coppia in esame e' incompleto (ad es. n=15)
                int dim2 = v.length - begin2;
                Comparable[] v1 = new Comparable[dim];
                Comparable[] v2 = new Comparable[dim2];
                System.arraycopy(v, begin1, v1, 0, dim);
                System.arraycopy(v, begin2, v2, 0, dim2);
                Comparable[] v3 = new Comparable[dim + dim2];
                merge(v3, v1, v2);
                System.arraycopy(v3, 0, v, begin1, v3.length);
            }
        }
    }

    private static void merge(Comparable[] v, Comparable[] v1, Comparable[] v2)
    {
        int i = 0;
        int i1 = 0;
        int i2 = 0;
        while (i1 < v1.length && i2 < v2.length)
            if (v1[i1].compareTo(v2[i2]) < 0)
                v[i++] = v1[i1++];
            else
                v[i++] = v2[i2++];
        while (i1 < v1.length)
            v[i++] = v1[i1++];
        while (i2 < v2.length)
            v[i++] = v2[i2++];
    }
}