public class mergeSort {

    public static void main(String args[]) {

        int zahlen[] = {9 ,4 ,5, 8};
        int [] ausgabe = new int[zahlen.length];

        for (int i = 0; i < zahlen.length; i++) {
            System.out.print(zahlen[i] + "  ");
        }
        System.out.println();
        ausgabe = mergeSort_sort(zahlen, 0, zahlen.length - 1);
        System.out.print("sorted:\n");
        for (int i = 0; i < zahlen.length; i++) {
            System.out.print(ausgabe[i] + "  ");
        }
        System.out.println();
    }

    public static int[] mergeSort_sort(int zahlen[], int min, int max) {


        int low = min;
        int high = max;
        int[] tmp = new int[high+1]; //high als Größe auf Grund der Rekursion
        //Kopieren des Arrays in tmp
        for (int i = 0; i < tmp.length; i++) {
            tmp[i] = zahlen[i];
        }

        if (low >= high) { // Abbruchbedingung der Rekursion
            return zahlen;
        } else {
            int middle = (low + high) / 2;

            mergeSort_sort(tmp, low, middle); //Übergabe der linken Liste an mergeSort_sort
            mergeSort_sort(tmp, middle + 1, high); //Übergabe der rechten Liste an mergeSort_sort

            int end_low = middle; // Ende linke Liste
            int start_high = middle + 1; // Anfang rechte Liste
            int a = 0;

            //Vergleichen und einfügen
            while ((low <= end_low) && (start_high <= high)) {
                if (tmp[low] < tmp[start_high]) {
                    zahlen[a] = tmp[low];
                    a++;
                    low++;
                } else {
                    zahlen[a] = tmp[start_high];
                    a++;
                    start_high++;
                }
            }
            // Rest linker Liste einfügen
            while (low < end_low) {
                zahlen[a] = tmp[low];
                a++;
                low++;
            }
            // Rest rechter Liste einfügen
            while (start_high < high-1) {
                zahlen[a] = tmp[high];
                a++;
                high++;
            }
            return zahlen;
        }
    }
}