package pkg;

import java.util.ArrayList;
import java.util.List;

public class MergeSort {

    public static List<Integer> mergeSort(List<Integer> elements, boolean rev) {
        int size = elements.size();
        if(size == 1 || size == 0) return elements;
        List<Integer> e1, e2;
        if(size % 2 == 0) {
            e1 = mergeSort(elements.subList(0, (size/2)), rev);
            e2 = mergeSort(elements.subList(size/2, size), rev);
        } else {
            e1 = mergeSort(elements.subList(0, (size/2) + 1), rev);
            e2 = mergeSort(elements.subList((size/2) + 1, size), rev);
        }
        List<Integer> ret = new ArrayList<Integer>();
        int i = 0, j = 0;
        while(i < e1.size() || j < e2.size()) {
            if(i >= e1.size()) { ret.add(e2.get(j)); j++; }
            else if(j >= e2.size()) { ret.add(e1.get(i)); i++; }
            else {
                if(rev ? e1.get(i) < e2.get(j) : e1.get(i) > e2.get(j)) { ret.add(e2.get(j)); j++; }
                else { ret.add(e1.get(i)); i++; }
            }
        }
        return ret;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        List<Integer> l = new ArrayList<Integer>();
        l.add(10);
        l.add(3);
        l.add(1);
        l.add(6);
        l.add(9);
        l.add(0);
        l.add(2);
        l.add(7);
        l.add(5);
        l.add(8);
        l.add(4);
        System.out.println(l.toString());
        System.out.println(mergeSort(l, false).toString());

    }

}