자바[JAVA] - 병합/합병 정렬 [Merge sort]

서론

백준에서 재귀 관련 문제를 풀다가 병합/합병 정렬[Merge sort] 을 처음 보았다.
이전에 정렬에 대해 공부했을때 여러가지를 보았지만 새로운 정렬 방법을 알게되어서 좋은 경험이였습니다!!😀
이번에 병합 정렬에 대해 공부한 내용을 정리해보려고합니다.

---

Merge sort[병합 정렬] 이란??

• 병합이란 두개 이상의 사물을 하나로 합친다는 뜻이다. 즉 병합 정렬은 문제를 분할하고 분할한 문제를 재귀적으로 정렬 후, 정렬된 배열을 병합(Merge)하여 정렬된 배열을 만드는 방식이다.
• 분할정복 알고리즘을 기반으로 하는 정렬 방법이다.
• 시간 복잡도는 평균, 최악, 최선 모두 O(n log n)으로 매우 안정적인 성능을 가지고 있다.

---

합병 정렬의 주요 단계

1. 분할(Divide): 배열을 계속해서 절반으로 나누는 과정입니다. 더 이상 나눌 수 없는 작은 단위까지 분할합니다.
2. 정복(Conquer): 더 이상 나눌 수 없는 작은 배열들을 정렬합니다. 두 개씩 짝을 지어 비교 후 정렬합니다.
3. 병합(Merge): 정렬된 배열들을 다시 병합하여 더 큰 배열로 만듭니다. 이 과정이 반복되며 최종적으로 정렬된 하나의 배열이 완성됩니다.

---

합병 정렬의 작동 방식

1. 배열을 더 이상 나눌 수 없을 때까지 절반으로 나눈다.
2. 각 부분 배열을 정렬된 상태로 병합한다.
3. 병합한 배열은 다시 상위 배열로 합쳐지며, 최종적으로 완전히 정렬된 배열이 된다.

---

합병 정렬의 장점과 단점

장점

• 안정적인 정렬 알고리즘 (동일한 값의 순서가 유지됨)
• 최악의 경우에도 O(n log n)의 시간 복잡도를 가짐
• Linked List와 같은 연결 리스트 자료구조에서 효율적으로 작동

단점

• 추가적인 메모리 공간이 필요함 (배열을 병합하는 과정에서 임시 배열이 필요)

---

예시로 구현한 Merge Sort 순서도

예시 데이터

[38, 27, 43, 3, 9, 82, 10, 45]

Step 1: 분할 (Divide)
배열을 계속 반으로 나눕니다. 먼저 배열을 반으로 나누면

//더 이상 배열을 나눌 수 없을 때까지 계속됩니다.

[38]    [27]    [43]    [3]    [9]    [82]    [10]    [45]

Step 2: 병합 (Merge)
병합하는 단계에서는 각 배열을 정렬하며 결합합니다.

//	1.먼저 [38]과 [27]을 비교하고, 작은 값을 먼저 넣어줍니다.

[38], [27] -> [27, 38] 

//	2.다음으로 [43]과 [3]도 병합합니다.

[43], [3] -> [3, 43]

//	3.다른 그룹들도 병합합니다.

[9], [82] -> [9, 82]
[10], [45] -> [10, 45]

//	4.이제 병합된 배열을 다시 결합합니다.

[27, 38], [3, 43] -> [3, 27, 38, 43]
[9, 82], [10, 45] -> [9, 10, 45, 82]

//	5.마지막으로 두 배열을 병합하면 최종 정렬된 배열이 됩니다.

[3, 27, 38, 43], [9, 10, 45, 82] -> [3, 9, 10, 27, 38, 43, 45, 82]

---

<Java로 구현한 Merge sort>

public class Merge_sort {
    static int[] temp, arr;

    // Merge Sort 메소드
    private static void merge_sort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2; // 배열의 중앙 구하기
            merge_sort(arr, left, mid); // 전반부 정렬
            merge_sort(arr, mid + 1, right); // 후반부 정렬
            merge(arr, left, mid, right); // 병합 작업
        }
    }

    // 병합 메소드
    private static void merge(int[] arr, int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        int k = left;

        // 병합 과정
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }

        // 왼쪽 배열에 남은 요소 처리
        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        // 오른쪽 배열에 남은 요소 처리
        while (j <= right) {
            temp[k++] = arr[j++];
        }

        // 병합된 결과를 원본 배열에 복사
        for (int index = left; index < k; index++) {
            arr[index] = temp[index];
        }
    }

    // 메인 메소드
    public static void main(String[] args) {
        // 정렬할 배열 초기화
        arr = new int[]{38, 27, 43, 3, 9, 82, 10, 45};
        temp = new int[arr.length]; // 임시 배열 초기화

        System.out.println("정렬 전 배열:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();

        // Merge Sort 호출
        merge_sort(arr, 0, arr.length - 1);

        System.out.println("정렬 후 배열:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

예시 실행 결과

정렬 전 배열:
38 27 43 3 9 82 10 45 
정렬 후 배열:
3 9 10 27 38 43 45 82