5. 병합 정렬(Merge Sort)

 
public class Main {
 
    static int[] sorted = new int[8];
 
    public static void main(String[] args) {
 
        int[] arr = { 6, 5, 9, 8, 7, 4, 2, 1 };
 
        mergeSort(arr, 0, arr.length - 1);
 
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
 
    private static void merge(int[] a, int start,int middle, int end) {
 
        int i = start;
        int j = middle + 1;
        int k = start;
 
        // 작은 순서대로 배열에 삽입하는 과정
        while(i <= middle && j <= end) {
            if(a[i] <= a[j]) {
                sorted[k] = a[i];
                i++;
            } else {
                sorted[k] = a[j];
                j++;
            }
            k++;
        }
        // 남은 데이터 삽입
        if( i > middle) {
            for(int n = j; n <=middle; n++){
                sorted[k] = a[n];
                k++;
            }
        } else {
            for(int n = i; n <=middle; n++){
                sorted[k] = a[n];
                k++;
            }
        }
 
        // 정렬된 배열을 삽입
        for(int n = start; n <= end; n++) {
            a[n] =sorted[n];
        }
    }
 
    private static void mergeSort(int[] a, int start, int end) {
 
        // 크기가 1보다 큰 경우
        if(start < end) {
            int middle = (start + end) / 2; // 중간값
            mergeSort(a, start, middle); // 중간값에서 왼쪽으로 병합정렬
            mergeSort(a, middle + 1, end); // 중간값에서 오른쪽으로 병합정렬
            merge(a, start, middle, end); // 정렬된 두개의 배열을 합쳐준다.
        }
 
    }
}
 

병합 정렬은 전체 원소를 하나의 단위로 분할한 후 분할한 원소를 다시 병합하는 정렬 방식.

 

병합 정렬은 분할한 원소를 담을 배열공간을 만들어야하기 때문에 메모리 활용이 비효율적인 문제가 있다.

병합 정렬은 퀵정렬보다 느리지만 시간복잡도(N * logN)을 보장한다. (효율적인 알고리즘)

 

병합 정렬은 다음과 같이 작동한다. (위키백과 참조)

1. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
2. 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 정복(conquer) : 각 부분 리스트를 재귀적으로 병합 정렬을 이용해 정렬한다.
4. 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다.
5. 복사(copy) : 임시 배열에 저장된 결과를 원래 배열에 복사한다.