private static <T extends Comparable<? super T>> void divideAndMerge(List<T> input) {
        if (input.size() <= 1) {
            return;
        }
        int size = input.size();
        List<T> l1 = new ArrayList<T>(input.subList(0, size / 2));
        List<T> l2 = new ArrayList<T>(input.subList(size / 2, size));
        divideAndMerge(l1);
        divideAndMerge(l2);
        input.clear();
        int i = 0, j = 0;
        for (int k = 0; k < size; k++) {
            T o1 = l1.get(i);
            T o2 = l2.get(j);
            T smaller = null;
            if (o1.compareTo(o2) < 0) {
                smaller = o1;
                i++;
            } else {
                smaller = o2;
                j++;
            }
            input.add(smaller);
            if (i == l1.size()) {
                input.addAll(k + 1, l2.subList(j, l2.size()));
                k = size;
            } else if (j == l2.size()) {
                input.addAll(k + 1, l1.subList(i, l1.size()));
                k = size;
            }
        }
    }