병합 정렬 (Merge Sort) 총 정리 - 개념, 원리, 동작 예시, 시간복잡도, C언어, Java, Python 예시코드, 주의점, 장단점

병합 정렬(Merge Sort)

 

1. 병합 정렬이란?

병합 정렬은 "분할 정복(Divide and Conquer)" 기법을 이용한 정렬 알고리즘으로, 리스트를 반으로 나누고 각각을 재귀적으로 정렬한 후 병합하여 정렬된 리스트를 만드는 방식입니다. 안정 정렬에 속하며, 대규모 데이터에서 특히 효율적입니다.

---

 

 

2. 원리

1. 배열을 두 부분으로 나눕니다.
2. 각 부분을 재귀적으로 병합 정렬합니다.
3. 두 정렬된 부분을 하나로 병합합니다.

---

 

 

3. 동작 예시 (구체적인 설명)

정렬할 배열: [38, 27, 43, 3, 9, 82, 10]

1. 배열 분할:
   • [38, 27, 43, 3]와 [9, 82, 10]으로 나눕니다.
2. 왼쪽 부분 [38, 27, 43, 3] 정렬:
   • 다시 [38, 27]과 [43, 3]으로 나눕니다.
   • [38, 27]은 [27, 38]로 정렬.
   • [43, 3]은 [3, 43]로 정렬.
   • 두 부분을 병합: [27, 38, 3, 43] → [3, 27, 38, 43].
3. 오른쪽 부분 [9, 82, 10] 정렬:
   • [9]과 [82, 10]으로 나눕니다.
   • [82, 10]은 [10, 82]로 정렬.
   • 두 부분을 병합: [9, 10, 82].
4. 최종 병합:
   • 왼쪽 [3, 27, 38, 43]과 오른쪽 [9, 10, 82] 병합.
   • 결과: [3, 9, 10, 27, 38, 43, 82].

반응형

---

 

 

4. 시간 복잡도

• 최선의 경우: O(n log n)
• 평균적인 경우: O(n log n)
• 최악의 경우: O(n log n)

---

 

 

5. 코드 예제

C 코드

#include <stdio.h>

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int L[n1], R[n2];
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

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

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, 0, n - 1);

    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

 

Java 코드

public class MergeSort {

    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;

            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            merge(arr, left, mid, right);
        }
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] L = new int[n1];
        int[] R = new int[n2];

        for (int i = 0; i < n1; i++)
            L[i] = arr[left + i];
        for (int j = 0; j < n2; j++)
            R[j] = arr[mid + 1 + j];

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

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

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};

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

        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

 

Python 코드

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2

        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0

        while i < len(L) and j < len(R):
            if L[i] <= R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

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

arr = [38, 27, 43, 3, 9, 82, 10]
merge_sort(arr)
print(arr)

---

 

 

6. 주의점

1. 재귀 호출이 많아질 수 있으므로, 스택 오버플로우에 주의해야 합니다.
2. 메모리 사용량이 많아질 수 있으므로, 제한된 환경에서는 적합하지 않을 수 있습니다.

---

 

 

7. 장단점

장점

• 시간 복잡도가 안정적: O(n log n).
• 안정 정렬로, 동일한 값의 순서가 유지됨.
• 대규모 데이터 정렬에 적합.

단점

• 추가적인 메모리 공간이 필요함.
• 구현이 다소 복잡함.

 

 

함께 보면 좋은 글

코딩 테스트에 나오는 거의 모든 정렬 알고리즘들에 대해 비교했습니다. 언제 어떤 정렬 알고리즘을 쓰면 좋은지에 대해서도 작성했습니다. 아래 링크에 자세히 작성했습니다.

 

2025.01.03 - [알고리즘] - 정렬 알고리즘 총 정리 및 비교 - 각 알고리즘 별 장단점, 시간 복잡도, 공간 복잡도, 안정성, 주요 특징, 상황에 따른 선택 기준

정렬 알고리즘 총 정리 및 비교 - 각 알고리즘 별 장단점, 시간 복잡도, 공간 복잡도, 안정성, 주