정렬 - 병합정렬

병합정렬

• 재귀용법을 이용한 정렬 알고리즘

병합정렬 방법

1. 리스트를 반으로 나눠서 비슷한 크기의 리스트로 나눈다.
2. 각 부분 리스트를 재귀함수로 합병 정렬을 이용해 정렬한다.
3. 두 부분리스트를 하나로 합친다.

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))));


    }

}