public class A24 {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        List<Integer> l = new ArrayList<Integer>();
        l.add(4);
        l.add(3);
        l.add(9);
        sort(l);
        System.out.print(l);

    }

    static public <T extends Comparable<T>> void sort(List<T> a) {
        sortR(a, 0, a.size()-1);
    }

    private static <T extends Comparable<T>> void sortR(List<T> a, int p, int r) {
        if (r <= p) {
            return;
        }
        int q = (r + p) / 2;
        sortR(a, p, q);
        sortR(a, q + 1, r);
        merge(a, p, q, r);
    }

    private static <T extends Comparable<T>> void merge(List<T> a, int p, int q, int r) {
        int p1 = p; //runs through left part
        int p2 = q + 1; //runs through right part
        int d = 0;
        List<T> temp = new ArrayList<T>((r - p) + 1);
        while (p1 <= q && p2 <= r) {
            if (a.get(p1).compareTo(a.get(p2)) <= 0) {
                temp.set(d++, a.get(p1++));
            } else {
                temp.set(d++, a.get(p2++));
            }
        }
        while (p1 <= q) {
            temp.set(d++, a.get(p1++));
        }
        while (p2 <= r) {
            temp.set(d++, a.get(p2++));
        }
        for (int i = 0; i <= r - p; i++) {
            a.set(p + 1, temp.get(i));
        }

    }

}