정렬 알고리즘 - 병합 정렬 (Merge sort)

 

 

병합 정렬 (Merge sort) 이란?

 

 

병합정렬(Merge Sort)은 분할정복 알고리즘의 일종으로, 주어진 배열을 반으로 나눈 뒤 각 부분 배열을 재귀적으로 정렬하고 병합하는 과정을 반복하여 전체 배열을 정렬하는 알고리즘입니다.

 

병합정렬은 아래와 같은 과정으로 진행됩니다.

1. 분할(Divide) : 입력 배열을 절반으로 나눕니다. 이 과정은 배열을 가능한 한 작은 크기의 부분 배열로 분할합니다.
2. 정복(Conquer) : 분할된 부분 배열을 재귀적으로 정렬합니다. 각 부분 배열은 더 이상 분할할 수 없을 때까지 정렬됩니다.
3. 병합(Combine): 정렬된 부분 배열을 다시 하나의 배열로 병합합니다. 이 때, 정렬된 부분 배열을 비교하여 정렬된 새로운 배열을 만듭니다.

병합정렬은 주어진 배열을 반으로 나누어 정렬하는 방식을 사용하여 효율적으로 정렬을 수행합니다.

 

 

병합 정렬 코드 예시 (C#)

 

아래 코드는 C#으로 작성된 병합정렬을 구현한 예시입니다. 입력된 배열 { 12, 11, 13, 5, 6, 7 }을 병합 정렬 알고리즘을 사용하여 재귀적으로 배열을 분할하고 병합하는 과정을 수행합니다.

 

using System;

class MergeSort {
    public static void Sort(int[] arr) {
        if (arr.Length <= 1)
            return;

        int middle = arr.Length / 2;
        int[] left = new int[middle];
        int[] right = new int[arr.Length - middle];

        Array.Copy(arr, 0, left, 0, middle);
        Array.Copy(arr, middle, right, 0, arr.Length - middle);

        Sort(left);
        Sort(right);
        Merge(arr, left, right);

        // Print the sorting process
        PrintMergeSortProcess(arr, left, right);
    }

    private static void Merge(int[] arr, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;

        while (i < left.Length && j < right.Length) {
            if (left[i] <= right[j])
                arr[k++] = left[i++];
            else
                arr[k++] = right[j++];
        }

        while (i < left.Length)
            arr[k++] = left[i++];

        while (j < right.Length)
            arr[k++] = right[j++];
    }

    // Print the merge sort process
    static void PrintMergeSortProcess(int[] arr, int[] left, int[] right) {
        Console.WriteLine("Left Array: " + string.Join(", ", left) + " | " +"Right Array: " + string.Join(", ", right));
        Console.WriteLine("Merged Result: " + string.Join(", ", arr));
        Console.WriteLine("------------------------------------------");
    }
}

class Program {
    static void Main(string[] args) {
        int[] arr = { 12, 11, 13, 5, 6, 7 };

        Console.WriteLine("Original Array:");
        PrintArray(arr);
        Console.WriteLine();
        
        MergeSort.Sort(arr);

        Console.WriteLine("\nSorted Array:");
        PrintArray(arr);
    }

    static void PrintArray(int[] arr) {
        foreach (int num in arr)
            Console.Write(num + " ");
        Console.WriteLine();
    }
}

 

위 코드를 실행한 결과는 다음과 같습니다.

 

Original Array:
12 11 13 5 6 7 

Left Array: 11 | Right Array: 13
Merged Result: 11, 13
------------------------------------------
Left Array: 12 | Right Array: 11, 13
Merged Result: 11, 12, 13
------------------------------------------
Left Array: 6 | Right Array: 7
Merged Result: 6, 7
------------------------------------------
Left Array: 5 | Right Array: 6, 7
Merged Result: 5, 6, 7
------------------------------------------
Left Array: 11, 12, 13 | Right Array: 5, 6, 7
Merged Result: 5, 6, 7, 11, 12, 13
------------------------------------------

Sorted Array:
5 6 7 11 12 13

 

 

 

병합 정렬 장단점

 

- 장점

• 안정적인 정렬 방법으로 데이터의 분포에 영향을 덜 받습니다.
• 대규모 데이터에 대해서도 효율적으로 동작합니다
• 병합 정렬은 다른 정렬 알고리즘과 달리 입력 데이터에 상관없이 항상 O(n log n)의 시간 복잡도를 가집니다.

- 단점

• 추가적인 메모리 공간이 필요합니다.
• 재귀 호출에 따른 오버헤드가 발생할 수 있습니다.
• 배열을 나누는 과정에서 추가적인 연산이 필요합니다.

 

병합 정렬 사용 사례

 

• 대용량 데이터를 정렬할 때 주로 사용됩니다. 예를 들어, 대규모 데이터베이스의 정렬이나 대량의 파일 정렬에 적합합니다.
• 안정적인 정렬이 필요한 경우에 주로 사용됩니다. 데이터의 순서가 변경되면 안 되는 경우에 유용합니다.
  
  

병합 정렬은 데이터의 분포에 영향을 덜 받고 안정적인 정렬을 제공하는 등의 장점으로 인해 다양한 분야에서 사용되고 있습니다. 그러나 메모리 공간과 재귀 호출에 따른 오버헤드 등의 단점도 고려해야 합니다.