public class MergeSort extends MiniJava {
    public static List readList(int number) {
        // number = Anzahl zu lesender Elemente
        List res = null;
        for (int i = 0; i < number; ++i) {
            int x = read();
            res   = new List(x,res);
        }
        return res;
    }
    
    public static List merge(List a, List b) {
        if (b == null)
            return a;
        if (a == null)
            return b;
        if (b.info > a.info) {
            a.next = merge(a.next, b);
            return a;
        } else {
            b.next = merge(a, b.next);
            return b;
        }
    }
        
    public static List sort(List a) {
        if (a == null || a.next == null)
            return a;
        List b = a.half(); // Halbiere!
        a = sort(a);
        b = sort(b);
        return merge(a,b);
    }
    
    // Jetzt kommt das Hauptprogramm
    public static void main(String[] args) {
        int n = read("Länge der Liste");
        List l = readList(n);
        l = sort(l);
        write(""+l);
    } // end of main()    
}