병합 정렬 (Merge Sort)

알고리즘을 공부하는 학생들이나 취준생들은 이 정렬알고리즘이 꼭 필요할 때가 있다.

 

많고 많은 정렬 알고리즘 중에 하나를 선택해야한다면 이 병합 정렬을 공부해서 익혀두길 권장한다.

 

병합 정렬은 안정 정렬에 속하고, 분할 정복(devide & conquer) 알고리즘 중 하나이다.

 

구현 방법은 아래와 같다.

1. 배열의 길이가 한개가 될때까지 배열을 분할한다.

2. 각 부분의 배열을 재귀적으로 정렬한다.

3. 하나의 리스트가 될때까지 정렬한다.

 

음 위의 구현방법이 이해가 잘 안되면 아래그림을 보면 이해가 쑤욱 될것이다.

 

병합정렬의 가장 큰 장점은 입력데이터가 무슨 데이터이든 상관없이 일관되게 O(nlog₂n) 의 복잡도를 가진다는 것이다.

 

구현 방법은 아래와 같다.

public class MergeSort {
    private static int[] sorted ;

    public static void main(String args[]) {
        int[] data = {3, 5, 2, 1, 7, 4, 6};
        int[] result = mergeSort(data);

        for(int num : result) {
            System.out.println(num);
        }
    }

    private static void merge(int[] data, int left, int middle, int right) {
        int l = left;
        int r = middle +1;

        // 임시배열의 index
        int idx = left;

        while(l<=middle & r<=right) {
            if(data[l]<=data[r]) {
                sorted[idx] = data[l];
                l++;
            } else {
                sorted[idx] = data[r];
                r++;
            }
            idx++;
        }

        // 나머지 남은 데이터 채움
        if(l>middle) { //왼쪽이 먼저 다 채워졌을때
            for (int i = r; i <= right; i++) {
                sorted[idx] = data[i];
                idx++;
            }
        } else {
            for (int i = l; i <= middle; i++) {
                sorted[idx] = data[i];
                idx++;
            }
        }

        // 배열에 정렬된 값 넣기
        for(int i = left; i <= right; i++) {
            data[i] = sorted[i];
        }
    }

    private  static void mergeSort(int[] data, int left, int right) {

        // 분리된 리스트가 하나 이상인지 체크
        if(left < right) {
            int mid = (left + right) / 2; // 절반 위치

            mergeSort(data, left, mid); // 절반 중 왼쪽 부분
            mergeSort(data, mid + 1, right); // 절반 중 오른쪽 부분

            merge(data, left, mid, right);        // 병합작업
        }
    }

    public static int[] mergeSort(int data[]) {
        sorted = new int[data.length];
        mergeSort(data, 0, data.length-1);
        sorted = null;

        return data;
    }

}