병합정렬

public class MySplitSort {

    public ArrayList<Integer> splitFunc(ArrayList<Integer> dataList) {


        if (dataList.size() <= 1) {
            return dataList;
        }

        int medium = dataList.size() / 2;

        ArrayList<Integer> leftList = new ArrayList<Integer>();
        ArrayList<Integer> rightList = new ArrayList<Integer>();

        leftList = splitFunc(new ArrayList<>(dataList.subList(0, medium)));

        rightList = splitFunc(new ArrayList<>(dataList.subList(medium, dataList.size())));

        return mergeFunc(leftList, rightList);
    }

    public ArrayList<Integer> mergeFunc(ArrayList<Integer> leftList,ArrayList<Integer> rightList) {

        int leftPoint = 0;
        int rightPoint = 0;
        ArrayList<Integer> mergeList = new ArrayList<>();

        while (leftList.size() > leftPoint && rightList.size() > rightPoint) {

            if (leftList.get(leftPoint) < rightList.get(rightPoint)) {
                mergeList.add(leftList.get(leftPoint++));
            } else {
                mergeList.add(rightList.get(rightPoint++));
            }

        }

        while (leftList.size() > leftPoint) {
            mergeList.add(leftList.get(leftPoint++));
        }

        while (rightList.size() > rightPoint) {
            mergeList.add(rightList.get(rightPoint++));
        }

        return mergeList;
    }

    public static void main(String[] args) {

        MySplitSort mySplitSort = new MySplitSort();
        System.out.println( mySplitSort.splitFunc(new ArrayList<Integer>(Arrays.asList(4, 56, 7, 7, 3, 2, 1, 2))));


    }

}