정렬 알고리즘 (Sorting Algorithms) - 병합 정렬 (Merge Sort)

병합 정렬(Merge Sort)

병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 전략을 사용하는 안정 정렬 알고리즘입니다. 데이터를 작은 단위로 나눈 뒤, 정렬하며 병합하는 과정을 통해 정렬된 배열을 만들어냅니다.

---

1. 정렬 방식

1. 분할(Divide): 배열을 절반으로 나눕니다.
2. 정복(Conquer): 각 부분 배열을 재귀적으로 병합 정렬을 수행합니다.
3. 병합(Merge): 두 정렬된 배열을 병합하여 하나의 정렬된 배열로 만듭니다.

---

2. 특징

• 시간 복잡도:
  • 최선/평균/최악: O(n log ⁡n)
• 공간 복잡도: O(n) (추가적인 배열이 필요함)
• 안정 정렬: 같은 값의 요소들의 상대적 순서가 유지됨.

---

3. 동작 원리

예시: 배열 [38, 27, 43, 3, 9, 82, 10]

1. 분할: 배열을 나눔
   • [38, 27, 43, 3]와 [9, 82, 10].
   • 계속 나누면 [38], [27], [43], [3], [9], [82], [10].
2. 정렬 및 병합:
   • [38]과 [27] → [27, 38]
   • [43]과 [3] → [3, 43]
   • [9]과 [82] → [9, 82]
   • ...
3. 최종 병합:
   • 모든 병합 완료 시 [3, 9, 10, 27, 38, 43, 82].

---

4. Java 구현

import java.util.Arrays;

public class MergeSort {
    // Merge two subarrays
    private static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1; // Size of left subarray
        int n2 = right - mid;    // Size of right subarray

        // Temporary arrays
        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

        // Copy data to temporary arrays
        for (int i = 0; i < n1; i++) {
            leftArray[i] = arr[left + i];
        }
        for (int j = 0; j < n2; j++) {
            rightArray[j] = arr[mid + 1 + j];
        }

        // Merge the temporary arrays back into the original array
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (leftArray[i] <= rightArray[j]) {
                arr[k] = leftArray[i];
                i++;
            } else {
                arr[k] = rightArray[j];
                j++;
            }
            k++;
        }

        // Copy remaining elements of leftArray (if any)
        while (i < n1) {
            arr[k] = leftArray[i];
            i++;
            k++;
        }

        // Copy remaining elements of rightArray (if any)
        while (j < n2) {
            arr[k] = rightArray[j];
            j++;
            k++;
        }
    }

    // Main function for Merge Sort
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2; // Avoid overflow

            // Recursively sort both halves
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            // Merge the sorted halves
            merge(arr, left, mid, right);
        }
    }

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("Original Array: " + Arrays.toString(arr));

        mergeSort(arr, 0, arr.length - 1);

        System.out.println("Sorted Array: " + Arrays.toString(arr));
    }
}

---

5. Python 구현

def merge_sort(arr):
    if len(arr) > 1:
        # Find the middle of the array
        mid = len(arr) // 2

        # Split the array into two halves
        left_half = arr[:mid]
        right_half = arr[mid:]

        # Recursively sort both halves
        merge_sort(left_half)
        merge_sort(right_half)

        # Merge sorted halves
        i = j = k = 0

        # Copy data to original array from left_half and right_half
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        # Check for any remaining elements
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

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

# Example usage
if __name__ == "__main__":
    arr = [38, 27, 43, 3, 9, 82, 10]
    print("Original Array:", arr)

    merge_sort(arr)

    print("Sorted Array:", arr)

---

6. 최적화

• Iterative Merge Sort: 재귀 호출 대신 반복문으로 구현하여 공간 복잡도를 O(1)O(1)로 줄일 수 있음.
• In-place Merge: 추가 배열을 사용하지 않고 정렬(하지만 구현이 복잡해짐).

---

7. 장단점

장점:

• 안정 정렬: 같은 값의 상대적인 순서가 유지됩니다.
• 시간 복잡도 보장: 최악의 경우에도 O(n log⁡ n)의 성능을 보장합니다.

단점:

• 추가 메모리 필요: 병합 과정에서 O(n) 크기의 배열이 필요합니다.
• 작은 데이터셋에 비효율적: 데이터가 적으면 삽입 정렬보다 느릴 수 있습니다.

---

8. 병합 정렬의 응용

병합 정렬은 추가 메모리를 허용할 수 있고 안정 정렬이 필요할 때 주로 사용됩니다. 예를 들어, 대규모 데이터의 외부 정렬(External Sorting)에서 효과적입니다.