/*
Programmieren Sie in Java analog zu Aufgabe 4-1 eine Auswertung des
Algorithmus Mergesort (Sortieren eines Arrays von Ganzzahlen, wie ab
Folie 12 gezeigt). Gezählt werden sollen dabei die Anzahl der
Vergleiche und die Anzahl der
Zuweisungen ins Ausgabearray.
Erweitern Sie die Statistik außerdem um die Anzahl der Aufrufe der
Methode „mergeSort“. Erweitern Sie dazu die Klasse SortStatistik
um die Methoden setAufrufe und getAufrufe. Die statistischen Daten
sollen also vom Statistik-Objekt
mit folgenden Methoden erfragt werden können (Rückgabetyp jeweils
int): getAufrufe(), getVergleiche(), getArrayZuweisungen().
*/

public class MergeCount {
    private int[] aus;
    private int[] b;
    private int anz;
    private int aufrufe, vergleiche, arrayZuweisungen;
    private SortStatistik s;

    public SortStatistik sort(int[] ein){
        aus = ein;
        anz = ein.length;
        vergleiche = 0;
        aufrufe = 0;
        arrayZuweisungen = 0;

        b=new int[anz];
        mergeSort(0, anz-1);

        s = new SortStatistik();
        s.setDaten(aus);
        s.setArrayZuweisungen(arrayZuweisungen);
        s.setAufrufe(aufrufe);
        s.setVergleiche(vergleiche);
        return s;
    }

    public void mergeSort(int lo, int hi) {
        aufrufe++;
        if (lo<hi){
            int m=(lo+hi)/2;
            mergeSort(lo, m);
            mergeSort(m+1, hi);
            merge(lo, m, hi);
        }
    }
    void merge(int lo, int m, int hi){
        int i, j, k;
        // beide Hälften von a in Hilfsarray b kopieren
        for (i=lo; i<=hi; i++) {
            b[i]=aus[i];
        }
        i=lo; j=m+1; k=lo;
        // jeweils das nächstgrößte Element zurückkopieren
        while (i<=m && j<=hi) {
            if (b[i]<=b[j]) {
                vergleiche++;
                arrayZuweisungen++;
                aus[k++]=b[i++];
            } else {
                vergleiche++;
                arrayZuweisungen++;
                aus[k++]=b[j++];
            }
        }
        // Rest der vorderen Hälfte falls vorhanden zurückkopieren
        while (i<=m) {
            arrayZuweisungen++;
            aus[k++]=b[i++];
        }
        while (j<=hi) {
            arrayZuweisungen++;
            aus[k++]=b[j++];
        }
    }
    public int[] getAus() {
        return aus;
    }


    public class SortStatistik {
        private int[] daten;
        private int aufrufe, vergleiche, arrayZuweisungen;

        public void setAufrufe(int a) {
            aufrufe = a;
        }
        public int getAufrufe() {
            return aufrufe;
        }

        public void setDaten(int[] d){
            daten = d;
        }
        public int[] getDaten(){
            return daten;
        }
        public void setVergleiche(int v){
            vergleiche = v;
        }
        public int getVergleiche(){
            return vergleiche;
        }
        public void setArrayZuweisungen(int t){
            this.arrayZuweisungen = t;
        }
        public int getArrayZuweisungen(){
            return arrayZuweisungen;
        }
    }
}