[알고리즘] 병합 정렬(Merge Sort): 개념과 자바 예제 코드

병합 정렬 (Merge Sort) 쉽게 설명하기 😊

병합 정렬은 정렬 알고리즘 중 하나로, 데이터를 두 부분으로 계속 나누었다가 다시 합치면서 정렬하는 방법이에요. 🧩
쉽게 말해서, 큰 문제를 작은 문제로 나누고, 각 문제를 해결한 뒤 결과를 합치는 방식이에요. 이를 분할 정복(Divide and Conquer) 이라고 불러요! 🦸‍♂️

---

🛠️ 병합 정렬의 단계:

1. 분할(Divide): 데이터를 더 이상 나눌 수 없을 때까지 절반으로 쪼개요. ✂️
   예: [8, 4, 7, 1] -> [8, 4], [7, 1] -> [8], [4], [7], [1]
2. 정복(Conquer): 나눈 데이터들을 크기 순서대로 정렬하면서 하나로 합쳐요.
   예: [8], [4] -> [4, 8] / [7], [1] -> [1, 7]
3. 결합(Combine): 정렬된 조각들을 다시 하나로 합쳐요.
   예: [4, 8], [1, 7] -> [1, 4, 7, 8] 🥳

---

🧑‍💻 자바 코드 예제

// 병합 정렬 구현 😊
public class MergeSort {
    // 메인 함수: 실행 시작점 🏁
    public static void main(String[] args) {
        int[] array = {8, 4, 7, 1}; // 정렬할 배열 📦
        mergeSort(array, 0, array.length - 1); // 병합 정렬 호출 📞

        // 결과 출력 🎉
        System.out.println("정렬 결과: ");
        for (int num : array) {
            System.out.print(num + " "); // 정렬된 배열 출력
        }
    }

    // 병합 정렬 함수: 배열을 나누고 합치는 작업을 수행 ✂️
    public static void mergeSort(int[] array, int left, int right) {
        if (left < right) { // 더 나눌 수 있을 때만 실행
            int mid = (left + right) / 2; // 중간 인덱스 계산

            mergeSort(array, left, mid); // 왼쪽 반 정렬
            mergeSort(array, mid + 1, right); // 오른쪽 반 정렬

            merge(array, left, mid, right); // 나눈 배열 합치기 🤝
        }
    }

    // 두 배열을 합치는 함수 😊
    public static void merge(int[] array, int left, int mid, int right) {
        int[] temp = new int[right - left + 1]; // 임시 배열 🧳
        int i = left, j = mid + 1, k = 0;

        // 작은 값부터 임시 배열에 복사 🌟
        while (i <= mid && j <= right) {
            if (array[i] <= array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }

        // 남은 값을 임시 배열에 추가 🚀
        while (i <= mid) temp[k++] = array[i++];
        while (j <= right) temp[k++] = array[j++];

        // 임시 배열을 원래 배열에 복사 ✏️
        for (i = left, k = 0; i <= right; i++, k++) {
            array[i] = temp[k];
        }
    }
    //정렬 결과: 
    //1 4 7 8
}

---

🐍 파이썬 코드 예제

# 병합 정렬 구현 😊
def merge_sort(array):
    if len(array) > 1:  # 더 나눌 수 있을 때만 실행 ✂️
        mid = len(array) // 2  # 중간 지점 계산
        left_half = array[:mid]  # 왼쪽 반
        right_half = array[mid:]  # 오른쪽 반

        merge_sort(left_half)  # 왼쪽 재귀 호출
        merge_sort(right_half)  # 오른쪽 재귀 호출

        # 두 반을 병합하는 단계 🤝
        i = j = k = 0

        # 작은 값부터 병합 😊
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                array[k] = left_half[i]
                i += 1
            else:
                array[k] = right_half[j]
                j += 1
            k += 1

        # 남은 값 병합 🌟
        while i < len(left_half):
            array[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            array[k] = right_half[j]
            j += 1
            k += 1


# 실행 예제 😊
array = [8, 4, 7, 1]  # 정렬할 배열 📦
merge_sort(array)  # 병합 정렬 호출 📞
print("정렬 결과:", array)  # 결과 출력 🎉
정렬 결과: [1, 4, 7, 8]

---

🚀 코드는 어떻게 동작하나요?

1. 처음에는 입력된 배열 [8, 4, 7, 1] 을 두 부분으로 나눠요:
   • 왼쪽: [8, 4]
   • 오른쪽: [7, 1]
2. 각 부분을 다시 두 조각으로 나눠요:
   • [8, 4] -> [8], [4]
   • [7, 1] -> [7], [1]
3. 나뉜 조각들을 순서대로 합쳐요:
   • [8], [4] -> [4, 8]
   • [7], [1] -> [1, 7]
4. 마지막으로 두 부분을 합치며 정렬:
   • [4, 8], [1, 7] -> [1, 4, 7, 8]

결과적으로 오름차순으로 정렬된 배열을 얻게 돼요!

🌟 주요 포인트 요약:

• 병합 정렬은 안정적인 정렬 알고리즘이에요. 데이터 순서가 유지됩니다! 🛡️
• 시간 복잡도는 항상 O(n log n) 이라서 빠른 편이에요! 🚀
• 하지만 임시 배열이 필요해서 메모리를 좀 더 사용해요. 📂

2024.12.14 - [자료구조 및 알고리즘] - 퀵 정렬 (Quick Sort) 쉽게 이해하기 : 예시 코드

퀵 정렬 (Quick Sort) 쉽게 이해하기 : 예시 코드

2024.12.14 - [자료구조 및 알고리즘] - 삽입 정렬(INSERT SORT) 쉽게 이해하기 : 예시 코드

삽입 정렬(INSERT SORT) 쉽게 이해하기 : 예시 코드