[정렬] 병합 정렬

병합 정렬

문제를 분할하고, 분할한 문제를 정복하여 합치는 과정'

 

병합 정렬은 데이터를 '비교'하면서 찾기 때문에 '비교 정렬'이며 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하기 때문에 '제자리 정렬(in-place sort)이 아니다.' 정확히는 제자리 정렬로 구현할 수는 있지만 그 대신 성능을 일부 포기해야하며 매우 신중하게 구현되어야 한다.

 

병합정렬의 구조상 최대한 작게 문제를 쪼개어 앞의 부분리스트부터 차례대로 합쳐나가기 때문에 안정정렬(Stable Sort) 알고리즘이기도 하다.

 

합병 정렬의 전체적인 과정은 이렇다.

1. 주어진 리스트를 절반으로 분할하여 부분리스트로 나눈다. (Divide : 분할)

2. 해당 부분리스트의 길이가 1이 아니라면 1번 과정을 되풀이한다.

3. 인접한 부분리스트끼리 정렬하여 합친다. (Conqure : 정복)

여기서 주의할 점은 합병정렬의 구현이 반드시 2개의 부분리스트로 나누어야 한다는 점은 아니다.

 

어디까지나 가장 일반적으로 구현되는 방식이 절반으로 나누는 방식일 뿐이다. 보통 위와 같이 두 개의 부분리스트로 나누는 방식을 two-way 방식이라고 하니 참고하시면 좋을 듯 하다.

 

그러면 일단 두 개씩 나누어 부분리스트를 생성한다는 것은 이해했을 것이다. 문제는 두 부분리스트를 정렬하고 합치는 방식인데, 그리 어렵지 않으니 빠르게 알아보도록 하자.

 

일단 우리가 이해하고 있어야 할 점은 각각의 부분리스트는 '정렬된 상태'라는 점이다.

두 부분리스트를 합쳐서 정렬할 때 굳이 삽입, 버블 정렬 등을 활용할 필요가 없다는 것이다. 그럼 어떻게 정렬을해? 라고 묻는다면 각 부분리스트의 첫 번째 원소부터 순차적으로 비교만 해주면 된다.

코드

   //Top-Down
    public static void 병합정렬(int[] arr){
        sorted = new int[arr.length];

        병합정렬(arr, 0, arr.length-1);
        sorted=null;
    }
    public static void 병합정렬(int[] arr, int left, int right){
        if (left==right) return;

        int mid = (left+right)/2;
        병합정렬(arr,left,mid);
        병합정렬(arr,mid+1,right);

        병합정렬(arr, left, mid, right);
    }

    public static void 병합정렬(int[] arr, int left, int mid, int right){
        int leftStart = left;
        int rightStart = mid+1;
        int fillIdx = left;

        //왼쪽 부분 리스트, 오른쪽 부분리스트
        while (leftStart<=mid && rightStart<=right){
            if (arr[leftStart]<=arr[rightStart]){
                sorted[fillIdx++] = arr[leftStart++];
            }
            else {
                sorted[fillIdx++] = arr[rightStart++];
            }
        }

        if (leftStart>mid){
            while (rightStart<=right){
                sorted[fillIdx++] = arr[rightStart++];
            }
        }

        else {
            while (leftStart<=mid){
                sorted[fillIdx++] = arr[leftStart++];
            }
        }

        for (int i=left; i<=right; i++){
            arr[i] = sorted[i];
        }
    }

 

장점

1. 항상 두 부분리스트로 쪼개어 들어가기 때문에 최악의 경우에도 O(NlogN) 으로 유지가 된다.
2. 안정정렬이다.

단점

1. 정렬과정에서 추가적인 보조 배열 공간을 사용하기 때문에 메모리 사용량이 많다.
2. 보조 배열에서 원본배열로 복사하는 과정은 매우 많은 시간을 소비하기 때문에 데이터가 많을경우 상대적으로 시간이 많이 소요된다.

 

 

 

 

 

 

 

 

출처:

https://st-lab.tistory.com/179