[정렬] Merge Sort

병합 정렬의 개념

병합 정렬 수행도

병합 정렬이란?

하나의 리스트를 두 개의 균등한 크기로 최대한 분할하고 분할된 부분 리스트를 순서대로 합하는 방식이다.
분할된 리스트를 순서대로 합쳐서 담기 위한 자료구조가 추가적으로 필요하다.
가장 작은 단위로 절반씩 쪼갠 후 가장 작은 단위부터 다시 합쳐나가는데 이 합쳐나가는 과정에서 데이터가 정렬이 된다.

Divide and Conquer 

1. Merge Sort의 해결 전략
2. 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략  
3. Divide and Conquer 방식은 대개 재귀 호출을 이용하여 구현함

동작 방식과 구현

1. 데이터들을 절반으로 나눈다. (분할)

2. 데이터를 가장 작은 단위로 분해한 후 맨 밑에서 부터 차례대로 합병을 진행한다. (정복)

    2-1. 두개의 배열 중 하나라도 자신의 범위를 벗어날 때 까지 반복한다.

        2-1-1 . 두개로 나뉘어진 배열의 요소를 앞에서부터 차례대로 비교한다.

        2-1-2. 오름차순 정렬 기준으로 두개의 요소 중 작은 요소를 별개의 리스트에 삽입한다.

        2-1-3. 삽입된 요소를 가진 배열의 인덱스를 다음 칸으로 이동시킨다.

    2-2. 남아 있는 데이터들을 리스트에 모두 삽입한다.

두개의 나뉘어진 배열을 순차적으로 비교하여 정렬이 가능한 이유는 나뉘어진 배열이 이미 정렬이 되어있는 상태이기 때문이다.  

→ Method Stack은 후입선출이니까, 가장 마지막에 호출된 메서드가 먼저 완료되기 때문

구현 코드

    void merge(int left, int right, int mid) {
        int[] buffer = new int[right-left+1];
        int bufferIdx = 0, l = left, r = mid+1;
        while(l <= mid && r <= right) {
            if(numbers[l] < numbers[r]) {
                buffer[bufferIdx++] = numbers[l++];
            }
            else {
                buffer[bufferIdx++] = numbers[r++];
            }
        }

        while(l <= mid) {
            buffer[bufferIdx++] = numbers[l++];
        }

        while(r <= right) {
            buffer[bufferIdx++] = numbers[r++];
        }

        for(int i=left; i<=right; i++) {
            numbers[i] = buffer[i-left];
        }
    }

    void divide(int left, int right) {
        if(left < right) {
            int mid = (left + right)/2;
            divide(left, mid);
            divide(mid+1, right);
            merge(left, right, mid);
        }
    }

 

병합 정렬의 장단점

장점 

1. stable sort 방법이기 때문에, 두 개의 키값을 가지고 정렬을 시도할 수 있음

단점

1. 배열로 구성하게 된다면, 별도의 저장 공간이 필요함
2. 임시 배열에 데이터를 반복적으로 옮겨줘야 하며, 심지어 본래 배열로 복사까지 해야하므로 값의 이동이 많음

병합 정렬의  시간 복잡도

시간 복잡도

Recursion Tree를 그렸을 때 Tree의 높이(k)는

n/2^k = 1 이므로, k = lgn이다. 

 

Tree의 각 층은 데이터 수가 동일하게 n이므로 시간복잡도는

O(n * lgn)이다. 

 

퀵 정렬과 다르게 무조건 절반으로 배열을 나누기 때문에 평균, 최선, 최악 모두 동일하게 O(nlgn)이다.

 

퀵정렬과 합병정렬의 차이점

1. 퀵정렬 : 우선 피벗을 통해 정렬 → 영역을 쪼갬
2. 합병정렬 : 영역을 쪼갤 수 있을 만큼 쪼갬 → 정렬