자바로 구현한 병합 정렬 알고리즘 (merge sort)

분할정복 알고리즘으로 리스트를 두 개로 나누고 각 하위 리스트를 정렬한 후 각각을 하나로 합친다. 

  @Test
    public void mergeSortTest() {
        // divide-and-conquer 알고리즘
        // 리스트를 두 개로 나누고 각 하위 리스트를 정렬한 후 각각을 하나로 합친다.
        // 병합정렬 성능은 O(nlogn), 각각의 병합시간이 O(n)이다.
        // 왼쪽으로 나눈 리스트를 정렬하고 -> 오른쪽으로 나눈 리스트를 정렬한다.

        List<Integer> values = Arrays.asList(7,1,3,2,3,9,2,5);
        List<Integer> sorted = divide(values);
        System.out.println(sorted);
    }

    public List<Integer> divide(final List<Integer> values) {
        if (values.size() < 2) {
            return values;
        }

        int listSize = values.size();

        final List<Integer> leftHalf = values.subList(0, listSize / 2);
        final List<Integer> rightHalf = values.subList(listSize / 2, listSize);

        System.out.println("-- dividing..leftHalf : " + leftHalf + " , rightHalf : " + rightHalf);

        return conquer(divide(leftHalf), divide(rightHalf));
    }

    private List<Integer> conquer(final List<Integer> left, final List<Integer> right) {
        System.out.println("## merging.. leftHalf : " + left + " , rightHalf : " + right);
        int leftPtr = 0;
        int rightPtr = 0;

        final List<Integer> merged = new ArrayList<>(left.size() + right.size());

        int leftSize = left.size();
        int rightSize = right.size();

        while (leftPtr < leftSize && rightPtr < rightSize) {
            if (left.get(leftPtr) < right.get(rightPtr)) {
                merged.add(left.get(leftPtr));
                leftPtr++;
            } else {
                merged.add(right.get(rightPtr));
                rightPtr++;
            }
        }

        while (leftPtr < leftSize) {
            merged.add(left.get(leftPtr));
            leftPtr++;
        }

        while (rightPtr < rightSize) {
            merged.add(right.get(rightPtr));
            rightPtr++;
        }

        System.out.println("## merged : " + merged);

        return merged;
    }

-- dividing..leftHalf : [7, 1, 3, 2] , rightHalf : [3, 9, 2, 5] -- dividing..leftHalf : [7, 1] , rightHalf : [3, 2] -- dividing..leftHalf : [7] , rightHalf : [1] ## merging.. leftHalf : [7] , rightHalf : [1] ## merged : [1, 7] -- dividing..leftHalf : [3] , rightHalf : [2] ## merging.. leftHalf : [3] , rightHalf : [2] ## merged : [2, 3] ## merging.. leftHalf : [1, 7] , rightHalf : [2, 3] ## merged : [1, 2, 3, 7] -- dividing..leftHalf : [3, 9] , rightHalf : [2, 5] -- dividing..leftHalf : [3] , rightHalf : [9] ## merging.. leftHalf : [3] , rightHalf : [9] ## merged : [3, 9] -- dividing..leftHalf : [2] , rightHalf : [5] ## merging.. leftHalf : [2] , rightHalf : [5] ## merged : [2, 5] ## merging.. leftHalf : [3, 9] , rightHalf : [2, 5] ## merged : [2, 3, 5, 9] ## merging.. leftHalf : [1, 2, 3, 7] , rightHalf : [2, 3, 5, 9] ## merged : [1, 2, 2, 3, 3, 5, 7, 9] [1, 2, 2, 3, 3, 5, 7, 9]

 

병합정렬의 성능은 O(nlogn)이고 각각의 병합시간은 O(n)이며 각 재귀 호출은 주어진 리스트 숫자의 절반만큼만 발생한다는 사실을 다시 한번 기억하자.

출처 : JAVA 프로그래밍 면접 이렇게 준비한다