[알고리즘] 병합 정렬 MergeSort (Java 예제)

정렬 알고리즘이란?

정렬 알고리즘은 배열의 원소들을 조건에 맞게 순서대로 정렬하는 알고리즘입니다. 원소들이 어떤 순서로 들어오는지에 따라 적절한 정렬 알고리즘을 선택할 수 있습니다.

선택 기준

1. 시간 복잡도: 알고리즘이 실행되는 데 소요되는 시간
2. 공간 복잡도: 알고리즘이 사용하는 메모리의 양
3. 안전성 (Stability): 동일한 값의 원소들의 순서가 유지되는지 여부

정렬 알고리즘 종류와 시간 복잡도

정렬 알고리즘 종류	최선 시간 복잡도	평균 시간 복잡도	최악 시간 복잡도
BubbleSort (버블 정렬)	O(n)	O(n^2)	O(n^2)
SelectionSort (선택 정렬)	O(n^2)	O(n^2)	O(n^2)
InsertionSort (삽입 정렬)	O(n)	O(n^2)	O(n^2)
MergeSort (병합 정렬)	O(n log n)	O(n log n)	O(n log n)
RadixSort (기수 정렬)	O(nk)	O(nk)	O(nk)
QuickSort (퀵 정렬)	O(n log n)	O(n log n)	O(n^2)

 

현재 정렬을 사용할 때는 대부분 퀵 정렬을 사용합니다. 병합 정렬이 최악의 조건에서 더 빠를 것 같다고 생각할 수 있지만, 정렬 알고리즘을 선택할 때는 시간 복잡도뿐만 아니라 공간 복잡도도 고려해야 합니다.

병합 정렬은 메모리를 많이 사용하므로, 여러 가지를 고려하여 정렬 알고리즘을 선택해야 합니다.

 

 

 

MergeSort (병합 정렬)란?

병합 정렬은 배열을 분할하고 정렬한 후, 다시 합치는 과정을 통해 정렬을 수행하는 알고리즘입니다. 이는 분 divide, 정복 conquer, 병합 merge의 세 가지 단계로 이루어집니다.

기본 개념

1. 분할: 주어진 배열을 두 개의 하위 배열로 나누고, 각각의 하위 배열에 대해 병합 정렬을 재귀적으로 수행합니다. 하위 배열의 크기가 1이 될 때까지 분할합니다.
2. 정복: 하위 배열이 정렬된 상태에서, 두 하위 배열을 병합하여 하나의 정렬된 배열로 만듭니다.
3. 병합: 두 개의 정렬된 배열을 하나의 배열로 병합하는 과정에서 원소를 비교하며 정렬된 상태로 결과 배열에 추가합니다.

병합 정렬 예시

주어진 배열: [58, 27, 43, 9, 1, 22, 30]

1. 분할 단계
   • 1단계: 배열을 두 개의 하위 배열로 나눕니다.
     • [58, 27, 43], [9, 1, 22, 30]
   • 2단계: 첫 번째 하위 배열을 다시 나눕니다.
     • [58], [27, 43]
   • 3단계: 두 번째 하위 배열을 나눕니다.
     • [27], [43]
   • 4단계: 두 번째 하위 배열도 다시 나눕니다.
     • [9, 1], [22, 30]
   • 5단계: 두 개의 하위 배열을 각각 나눕니다.
     • [9], [1]
     • [22], [30]
2. 정렬 단계
   • 정렬된 하위 배열:
     • [58], [27], [43], [9], [1], [22], [30]
3. 병합 단계
   • 1단계: [27]와 [43]을 병합합니다.
     • 병합 결과: [27, 43]
   • 2단계: [9]와 [1]을 병합하여 정렬합니다.
     • 병합 결과: [1, 9]
   • 3단계: [22]와 [30]을 병합하여 정렬합니다.
     • 병합 결과: [22, 30]
   이제 중간 단계에서의 정렬된 하위 배열은 다음과 같습니다:
   • [58], [27, 43], [1, 9], [22, 30]
4. 최종 정렬된 배열
   • [1, 9, 22, 27, 30, 43, 58]

자바 코드

import java.util.Arrays;

public class MergeSort {

    public static void main(String[] args) {
        // 정렬할 배열을 정의합니다.
        int[] arr = {58, 27, 43, 9, 1, 22, 30};
        
        // mergeSort 함수를 호출하여 배열을 정렬합니다.
        mergeSort(arr, 0, arr.length - 1);
        
        // 정렬된 배열을 출력합니다.
        System.out.println(Arrays.toString(arr));
    }
    
    // 병합 정렬 함수
    public static void mergeSort(int[] arr, int left, int right) {
        // 배열의 왼쪽 인덱스가 오른쪽 인덱스보다 작은 경우에만 실행
        if (left < right) {
            // 중앙 인덱스를 계산합니다.
            int middle = (left + right) / 2;
            
            // 왼쪽 절반을 재귀적으로 정렬합니다.
            mergeSort(arr, left, middle);
            
            // 오른쪽 절반을 재귀적으로 정렬합니다.
            mergeSort(arr, middle + 1, right);
            
            // 정렬된 왼쪽 절반과 오른쪽 절반을 병합합니다.
            merge(arr, left, middle, right);
        }
    }

    // 두 개의 하위 배열을 병합하는 함수
    private static void merge(int[] arr, int left, int middle, int right) {
        // 왼쪽과 오른쪽 하위 배열의 크기를 설정합니다.
        int n1 = middle - left + 1; // 왼쪽 하위 배열의 크기
        int n2 = right - middle;     // 오른쪽 하위 배열의 크기
        
        // 임시 배열을 생성합니다.
        int[] leftArr = new int[n1];  // 왼쪽 하위 배열
        int[] rightArr = new int[n2]; // 오른쪽 하위 배열
        
        // 원본 배열에서 왼쪽 하위 배열에 원소를 복사합니다.
        for (int i = 0; i < n1; i++) {
            leftArr[i] = arr[left + i]; // arr의 left 인덱스부터 n1 개수만큼 복사
        }
        
        // 원본 배열에서 오른쪽 하위 배열에 원소를 복사합니다.
        for (int i = 0; i < n2; i++) {
            rightArr[i] = arr[middle + 1 + i]; // arr의 middle + 1 인덱스부터 n2 개수만큼 복사
        }
        
        // leftArr와 rightArr의 병합 과정
        int i = 0; // leftArr의 인덱스
        int j = 0; // rightArr의 인덱스
        int k = left; // 원본 배열의 현재 인덱스
        
        // 두 하위 배열을 병합하여 원본 배열에 정렬된 형태로 넣습니다.
        while (i < n1 && j < n2) { // 두 배열의 원소가 남아있을 때
            if (leftArr[i] > rightArr[j]) // 내림차순 정렬 (조건 수정으로 오름차순 정렬 가능)
                arr[k++] = rightArr[j++]; // 오른쪽 배열의 원소를 넣고 인덱스 증가
            else
                arr[k++] = leftArr[i++]; // 왼쪽 배열의 원소를 넣고 인덱스 증가
        }
        
        // 아직 남아있는 왼쪽 배열의 원소를 원본 배열에 추가합니다.
        while (i < n1) {
            arr[k++] = leftArr[i++]; // 왼쪽 배열의 원소를 넣고 인덱스 증가
        }
        
        // 아직 남아있는 오른쪽 배열의 원소를 원본 배열에 추가합니다.
        while (j < n2) {
            arr[k++] = rightArr[j++]; // 오른쪽 배열의 원소를 넣고 인덱스 증가
        }
    }
}

 

 

병합 정렬 장단점

장점

1. 안정성 (Stability):
   • 병합 정렬은 안정적인 정렬 알고리즘입니다.
   • 동일한 값을 가진 원소의 상대적인 순서를 유지합니다.
   • 이는 특히 데이터베이스나 애플리케이션에서 중요할 수 있습니다.
2. 예측 가능한 성능:
   • 최악의 경우 시간 복잡도가 O(n log n)으로, 다양한 입력에 대해 안정적으로 좋은 성능을 발휘합니다.
   • 이는 정렬할 데이터의 상태와 상관없이 일관된 결과를 제공합니다.
3. 분할 정복 전략:
   • 문제를 작은 하위 문제로 나누어 해결하는 방식이므로, 병렬 처리가 용이합니다.
   • 여러 프로세서에서 동시에 작업할 수 있어 대규모 데이터 처리에 적합합니다.
4. 큰 데이터 처리 가능:
   • 입력 데이터가 메모리에 다 들어가지 않는 경우에도 외부 정렬로 활용할 수 있습니다.
   • 디스크에서 직접 읽어들이고 정렬할 수 있어 대용량 데이터 처리에 유리합니다.

단점

1. 공간 복잡도:
   • 병합 정렬은 O(n)의 추가 메모리를 필요로 합니다.
   • 원본 배열을 나누어 하위 배열을 생성하고 병합하는 과정에서 임시 배열이 필요하므로 메모리 사용량이 늘어납니다.
   • 메모리 사용이 제한된 환경에서는 불리할 수 있습니다.
2. 비교 연산 비용:
   • 병합 정렬은 원소를 비교하면서 병합을 진행하므로 다른 정렬 알고리즘에 비해 비교 연산의 횟수가 많아질 수 있습니다.
   • 특히 데이터가 이미 정렬된 경우, 다른 알고리즘에 비해 성능이 떨어질 수 있습니다.
3. 직접적인 정렬에 비해 느림:
   • 다른 O(n log n) 정렬 알고리즘, 예를 들어 퀵 정렬에 비해 직접적인 성능이 떨어질 수 있습니다.
   • 작은 데이터 집합에서는 오히려 O(n^2) 알고리즘이 더 빠를 수 있습니다.
4. 복잡한 구현:
   • 알고리즘이 비교적 복잡하여 재귀 호출과 병합 과정을 정확하게 구현하는 데 주의가 필요합니다.
   • 따라서 초보자가 이해하고 구현하기 어려울 수 있습니다.