📒 갈무리 - 합병정렬(Merge Sort)

📌 합병정렬이란?

- O(N*LogN) 비교 기반 정렬 알고리즘이다.

- 일반적인 방법으로 구현했을 때 안정 정렬(Stable Sort)에 속하며, 분할 정복 알고리즘의 하나이다.

- 간단히 말하면, 일단 반으로 쪼갠 후 나중에 합치는 방식의 정렬이다.

 

📌 합병정렬 진행 순서

1. 전부 한 개씩 남을 때까지 반으로 나눈다.

2. 그 후, 두 집합씩 비교하고 합치는 순간에 부분 정렬한다.

3. 2번 순서를 계속 반복하며 최종 정렬을 완수한다.

 

📌 직접 구현해 보자...

// C#	
        private int number = 8;
        private int[] sorted = new int[8];

        public void Merge(int[] a, int m, int middle, int n)
        {
            int i = m;
            int j = middle + 1;
            int k = m;

            // 작은 순서대로 배열에 삽입
            while (i <= middle && j <= n)
            {
                if (a[i] <= a[j])
                {
                    sorted[k] = a[i];
                    i++;
                }
                else
                {
                    sorted[k] = a[j];
                    j++;
                }
                k++;
            }
            // 남은 데이터도 삽입
            if (i > middle)
            {
                for (int t = j; t <= n; t++)
                {
                    sorted[k] = a[t];
                }
            }
            else
            {
                for (int t = i; t <= middle; t++)
                {
                    sorted[k] = a[t];
                    k++;
                }
            }
            // 정렬된 배열을 삽입
            for (int t = m; t <= n; t++)
            {
                a[t] = sorted[t];
            }
        }

        public void MergeSort(int[] a, int m, int n)
        {
            if (m < n)
            {
                int middle = (m + n) / 2;
                MergeSort(a, m, middle);
                MergeSort(a, middle + 1, n);
                Merge(a, m, middle, n);
            }
        }

 

📌 합병정렬의 특징

- 퀵 정렬은 피봇값에 따라 편향되게 분할할 가능성 때문에 최악의 경우 O(n²)의 시간 복잡도를 가질 수 있다. 하지만 병합 정렬은 정확히 절반씩 나누어 진행된다는 점에서 최악의 경우에도 O(N*LogN)을 보장한다.

- 퀵 정렬보다 빠르진 않지만 퀵 정렬이 가지는 한계점을 보완한다.

- 기존의 데이터를 담을 추가적인 배열 공간이 필요하기 때문에 메모리 활용이 비효율적이다.