[Java] 병합 정렬 (Merge Sort) - 정렬 알고리즘 (Sorting Algorithm)

병합 정렬 (Merge Sort)

병합 정렬(Merge Sort)은 효율적이고 안정적인 정렬 알고리즘 중 하나로, 분할 정복(Divide and Conquer) 알고리즘을 따른다. 병합 정렬의 기본 개념은 다음과 같다.

• 분할(Divide) : 입력받은 배열을 절반으로 분할하고, 길이가 1이 될 때까지 분할을 반복한다.
• 정복(Conquer) : 각 분할된 배열에 대해 재귀적으로 정렬을 수행한다.
• 병합(Merge) : 분할한 배열을 병합하면서 정렬한다. 두 개의 정렬된 배열을 하나의 정렬된 배열로 합치는 과정으로 병합 과정에서 실제 정렬이 이루어진다.

병합 정렬의 시간 복잡도는 O(n log n)으로 길이가 긴 배열을 안정적으로 정렬할 때 적합한 알고리즘이다.

 

 

병합 정렬의 장단점

장점

• O(n log n)의 시간 복잡도를 가지고 있어 다른 정렬 알고리즘에 비해 효율적이다.
• 동일하 값의 원소가 입력에 따라 순서를 보장하는 안정 정렬(Stable Sort) 알고리즘이다.
• 최선과 최악의 경우에도 항상 동일한 시간 복잡도를 가진다.

 

단점

• 원본 배열을 분할하여 새로운 배열을 추가적으로 만들기 때문에 추가적인 메모리가 필요하다.
• 다른 정렬 알고리즘에 비해 구현하기가 복잡하다.
• 배열의 크기가 작은 경우 퀵 정렬과 같은 알고리즘이 더 빠르다.

 

병합 정렬은 여러 상황에 따라 적절하게 사용되어야 하는데, 제한된 메모리를 가진 환경에서는 다소 적합하지 않을 수 있다.

 

 

병합 정렬의 과정

 

 

구현

public class MergeSort {
    public void sort(int[] arr, int left, int right) {
        if (left == right) {
            return;
        }

        // 중간 인덱스
        int mid = (left + right) / 2;

        // 왼쪽 정렬
        sort(arr, left, mid);
        // 오른쪽 정렬
        sort(arr, mid + 1, right);

        // 배열 합치기
        merge(arr, left, mid, right);
    }

    public void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1; // 왼쪽 배열의 길이
        int n2 = right - mid; // 오른쪽 배열의 길이

        // 왼쪽 배열 오른쪽 배열
        int[] leftTemp = new int[n1];
        int[] rightTemp = new int[n2];

        // 왼쪽 배열 담기
        for (int i = 0; i < n1; i++) {
            leftTemp[i] = arr[left + i];
        }
        // 오른쪽 배열 담기
        for (int i = 0; i < n2; i++) {
            rightTemp[i] = arr[mid + 1 + i];
        }

        // 왼쪽 배열과 오른쪽 배열의 인덱스
        int i = 0, j = 0;
        // 원본 배열 arr의 시작 인덱스
        int k = left;

        // 원본 배열에 정렬
        while (i < n1 && j < n2) {
            if (leftTemp[i] <= rightTemp[j]) {
                arr[k] = leftTemp[i];
                i++;
            } else {
                arr[k] = rightTemp[j];
                j++;
            }
            k++;
        }

        // 남아 있는 요소 담기
        while (i < n1) {
            arr[k] = leftTemp[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = rightTemp[j];
            j++;
            k++;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        int[] array = {38, 27, 43, 3, 9, 82, 10};
        MergeSort mergeSort = new MergeSort();
        
        mergeSort.sort(array, 0, array.length - 1);

        for (int i : array) {
            System.out.print(i + " ");
        }
    }
}

// 출력
3 9 10 27 38 43 82