병합정렬(Merge Sort)

병합정렬

Merge Sort 는 Java Collection API 에서도 사용하는 것으로 알고있을 정도로 안전하다. 가끔 왜 Quick Sort 를 쓰지않고, Merge Sort 를 사용하여 구현하는 것에 대한 이야기가 있는데
Quick Sort 를 구현해봤다면 Quick sort 는 stability 하지 않다는 것을 알것이다. 따라서 충분히 objcet 의 경우에 sort 에서 순서가 뒤바뀌는 현상을 경험하기 충분하며 그로인한 사이드 이펙트를 유발할 수 있다.
일단 이 얘기는 뒤로하고 알고리즘에 대해 알아보도록 하자.

도식

나는 이런 Recursive 하게 짜야되는 Algorithm 을 작성할때는 항상 도식을 그리는 편이다. 그래야 Call Stack 생각도 잘나고, 코드도 잘 작성되는 것 같다.
일단 기본적으로 메커니즘은 배열이 있다면 완전하게 정렬될때 까지 반으로 나누고, 완전히 정렬했다면 합치는 방식이다.

Base Algorithm

1.주어진 배열이 완전히 정렬되었는가?

1.NO 합친다.

1.YES 정렬을 middle pos 기반으로 divide 한다. -> 다시 1번으로 돌아간다.

위의 알고리즘을 한번 보고, 그림을 보면 약간은 이해가 갈 것이다. 그래도 아직 이해가 안갔을 확률이 높다.

생각해보기

일단 코드자체를 봤을때 계속해서 recursive 하게 devide() 라는 function 을 탈것만 같은 기분이다. 그리고 그 devide() 에는 completed sorted array 인지 확인하기 위한 if condition 문장또한 존재할 것이다. 다만 여기서 if (completed sorted array) {combine()} 라는 코드가 나올지는 고민을 해봐야 한다. 왜냐하면, 저 위의 도식에서 CallStack 을 보면 combine 할때는 항상 left array 와 right array 가 정렬되어 있기 때문이다. Recursive 하게 생각할때는 이런 마인드셋이 중요하니까, 이 문장을 잘 이해해야 한다. 그래서 코드는 다음과 같이 나올것이다.

    private void divide(int[] nums, int left, int right) {
        if (isCompletedSort(left, right)) {
            int middle = (left + right) / 2;
            divide(nums, left, middle);
            divide(nums, middle + 1, right);
            combine(nums, left, middle, right);
        }
    }

    private boolean isCompletedSort(int left, int right) {
        return left < right
    }

위의 sudo code 를 보면 알겠듯이 divide 를 통해서 계속해서 나눈다. 이는 위의 도식에서 completed sort 가 될때까지 지속될것이다. 즉, 배열이 한개가 됬다고 인식될때까지 계속된다. 이제 다시 merge 를 하기 위해서는 left 와 right 의 첫번째값을 비교하며, 둘중 작은것을 먼져 넣어주면 된다. 여기서 우리가 잡을 수 있는 변수는 아래처럼 될것이다.

• 넣는 위치 = inputIndex
• 비교할 왼쪽 인덱스(넣으면 한칸씩 이동할것이므로) = leftIndex
• 비교할 오른쪽 인덱스(넣으면 한칸씩 이동할것이므로) = rightIndex = 대부분의 상황에서는 middle + 1 일 것이다.

그래서 코드를 작성해보면 아래와 같다.

    private void combine(int[] nums, int left, int middle, int right) {
        int inputIndex = left;
        int leftIndex = left;
        int rightIndex = middle + 1;

        // merge
        while (leftIndex <= middle && rightIndex <= right) {
            if (nums[leftIndex] <= nums[rightIndex])
                tempArray[inputIndex++] = nums[leftIndex++];
            else
                tempArray[inputIndex++] = nums[rightIndex++];
        }

        if (leftIndex > middle) {
            for (int i = rightIndex; i <= right; i++) {
                tempArray[inputIndex++] = nums[i];
            }
        } else {
            for (int i = leftIndex; i <= middle; i++) {
                tempArray[inputIndex++] = nums[i];
            }
        }

        if (right + 1 - left >= 0) System.arraycopy(tempArray, left, nums, left, right + 1 - left);
    }

간단하게 설명하면 if (nums[leftIndex] <= nums[rightIndex]) 의 Condition 은 아래 사진 처럼 비교하는 것이다.

leftIndex 와 rightIndex 의 값중 작은 것을 임시 배열의 InputIndex에 넣어주고 InputIndex++, leftIndex++ 을 해준다.

시간복잡도

일단 시간복잡도는 O(nlogn) 이다. 이유는 간단한데 우리가 보통 정렬된 배열을 정렬하는데는 O(n) 만큼의 시간이 걸린다. 그래서 두개로 나눠진 정렬된 배열을 merge 하는 과정이 O(2N) 의 시간이 소요되게 된다. 우리가 Split 하는데 시간은 얼마나 걸릴까? 지금 보면 middle 로 나눠서 가면갈수록 반절씩 줄어드는 구조이다. 즉,O(logN) 번이 소모된다. 그래서 총 걸리는 시간은 O(2NlogN 인데, 시간복잡도에서 Constant 는 큰의미를 지니지 않으므로 O(NlogN) 이 된다.

공간복잡도

공간복잡도는 엄청 간단한데, 우리가 저 정렬을 하기 위해서는 똑같은 사이즈의 배열이 하나 더 필요하다. 그래서 공간복잡도는 O(N) 이다.

추가로 보면 좋은 문서

Why Java Collections sort uses mergeSort instead of quickSort ?

MyGithub

https://github.com/tmdgusya/udemy-algorithm/blob/main/src/main/java/sort/MergeSort.java