[JAVA] 병합정렬(Merge Sort) 개념과 코드 구현

병합 정렬(Merge Sort)은 비교 기반 정렬 알고리즘이다.

문제를 작은 여러 문제로 쪼개서 각각을 해결하고 결과를 모아서 원래 문제를 해결하는 방법이다.

안정 정렬이며 분할 정복 알고리즘의 하나이다.

• 안정 정렬: 반복되는 요소를 입력때와 동일한 순서로 정렬 시키는 정렬(중복된 부분은 순서가 유지되는 정렬)
• 분할 정복 알고리즘: 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법. 보통 재귀함수를 통해 구현된다.

구분	최악 시간복잡도	최선 시간복잡도	평균 시간복잡도	공간복잡도(메모리)	안정성
합병정렬	O(n log n)	O(n log n)	O(n log n)	O(n)	Y

알고리즘

1.  N개의 길이를 가진 배열 리스트를 각각 하나의 원소만 포함하는 N개의 부분 리스트로 분할한다.
2.  부분리스트가 하나만 남을때까지 반복해서 병합하며 정렬된 부분리스트를 생성한다. 

작동되는 세부적인 과정을 살펴보면 아래와 같이 작동한다.

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

좌측 그림과 같이 8개 인자를 1/2 씩 쪼개어 길이가 1인 리스트로 만들고,

각 부분리스트를 재귀적으로 병합 정렬을 이용해 정렬한다.

결국 모든 부분리스트가 합쳐져 다시 하나의 정렬된 리스트가 되면

해당 결과를 리턴하게 된다.

병합정렬은 재귀적 접근법(위 -> 아래)과 반복적 접근법(아래->위)으로 구현할 수 있다.

 

 

소스코드

// 1. 전체 기능을 총괄하는 메서드. 실제 비즈니스 메서드를 호출하는 지점
int[] mergeSort(int[] arr) {
    sort(arr, 0, arr.length - 1);
    return arr;
}

// 2. 배열을 반으로 나누어서 재귀호출해주는 메서드
void sort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;

        // 왼쪽 부분리스트에 재귀 함수 호출
        sort(arr, left, mid);
        // 오른쪽 부분리스트에 재귀 함수 호출
        sort(arr, mid + 1, right);
        // 두 부분리스트를 병합
        mergeArray(arr, left, mid, right);
    }
}

// 3. 두 배열을 순서대로 정렬해서 병합해주는 메서드
void mergeArray(int[] arr, int left, int mid, int right) {
    // 비교를 위해 임시 배열 정의 및 초기화(복사)
    int[] temp = new int[arr.length];
    System.arraycopy(arr, 0, temp, 0, arr.length);

    int leftIdx = left; // 두 배열의 인자 크기를 비교하기 위한 인덱스
    int rightIdx = mid + 1; // 두 배열의 인자 크기를 비교하기 위한 인덱스
    int idx = leftIdx; // 결과용 배열 왼쪽에서부터 순서대로 채워넣기 위한 인덱스

    while (leftIdx <= mid && rightIdx <= right) {
        // 두 부분리스트 인자의 크기를 비교해서 작은것을 결과용 배열에 넣어줌
        if (temp[leftIdx] <= temp[rightIdx]) {
            arr[idx++] = temp[leftIdx++];
        } else {
            arr[idx++] = temp[rightIdx++];
        }
    }

    // 만약 좌측 부분리스트에 인자가 남았을 경우 남은 요소를 처리해줌
    for (int i = 0; i <= mid - leftIdx; i++) {
        arr[idx + i] = temp[leftIdx + i];
    }
}

참고자료

Comparison Sorting Algorithms

합병 정렬

안정 정렬 vs 불안정 정렬