import java.util.Random;
public class MergeSort
{
    static Random r = new Random();
    static int[] a = new int[100];
    // gibt eine zufällige Zahl von 1-50 zurück 
    public static int Zufallszahl(){      
       return r.nextInt(10);
    }
    public static void main(){
        // array mit 20 zufallszahlen von 1-50 belegen 
       for (int i = 0; i < a.length; i++){
           a[i] = Zufallszahl();
       }
       // ausgeben des arrays "a"
       for (int i = 0; i < a.length; i++){
           System.out.print(a[i]);
           System.out.print(",");
       }
       System.out.println();
       
       a = sort(a);
       
       // ausgeben des arrays "a"
       for (int i = 0; i < a.length; i++){
           System.out.print(a[i]);
           System.out.print(",");
       }
    }
    public static int[] sort(int[] a){
        // 0. Schritt: Abbruchbedingung
            if (a.length == 1) return a;
        
        // 1. Schritt: auf 2 Arrays aufteilen
            int[] l = new int[a.length/2];
            int[] r = new int[a.length -l.length];
            for (int i = 0; i < a.length; i++){
                if (i <= a.length/2)l[i] = a[i];
                else r[i-l.length] = a[i];
            }
        // 2. Schritt Arrays sortieren (rekursiv)
            l = sort(l);
            r = sort(r);
            int links = 0;
            int rechts = 0;
        // 3. Schritt Arrays zusammenfügen
            for (int i = 0; i<a.length; i++){
                if(links >= l.length){      //links "leer"
                    a[i] = r[rechts];
                    rechts++;
                }else if (rechts >= r[rechts]){ //rechts "leer"
                    a[i] = l[links];
                    links++;
                }else if (l[links] <= r[rechts]){       // links größer
                    a[i] = l[links];
                    links++;
                }
                else{                   // rechts größer
                    a[i] = r[rechts]; 
                    rechts++;
                }
    }
    return a;
}
}