Merge Sort Algorithm (병합 정렬 알고리즘)

앞서 살펴본 Selection Sort(선택 정렬)와 Insertion Sort(삽입 정렬)은

입력 리스트의 크기가 크면 클수록 더욱 비 효율적인 단점을 갖고 있다. 

그래서 조금 더 나은 정렬법인 Merge Sort를 배워보도록 하겠다.

Divide and Conquer

Merge Sort에는 Divide and Conquer(나눠서 정복하기)라는 재귀에 기반한 알고리즘 양식이 적용된다.

이것은 문제를 원래의 문제와 비슷한 형식으로 자그마하게 쪼개서

작은 문제들을 재귀적으로 풀어내는 것이다.

Divide(나누기) : 큰 문제를 같은 방식으로 풀 수 있는 작은 문제로 쪼갠다.

Conquer(정복) : 작은 문제들을 재귀적으로 풀어낸다.

Combine(합치기) : 작은 문제들에서 얻어낸 해결책을 원래의 큰 문제에 적용시킨다.

이것을 Merge Sort에 적용시켜보면

p번째 부터 r번째 까지 정렬한다고 가정해보자. 

Divide : 임의의 수 p와 r 번째 중간에 있는 숫자 q를 찾는다. 이 과정을 이진 검색 알고리즘에서와 마찬가지로

p와 r을 더해서 나누고 반내림한 값으로 찾는다.

Conquer : Divide 단계에서 만들어지는 작은 리스트를 각각 재귀적으로 정렬한다.

Combine : 정렬된 작은 리스트들을 다시 p부터 r까지 합친다.

실제 코드로 바로 들어가보겠다.

Merge Sort in C#

namespace Rextester
{
    public class Program
    {
        public const int ITEMSIZE = 8;
        
        public static void Main(string[] args)
        {
            int[] array = new int[] {14, 7, 3, 12, 9, 11, 6 , 2};
            mergeSort(array, 0, ITEMSIZE - 1);
            printArray(array);
        }
        
        public static void printArray(int[] array) {
            foreach (int element in array) {
                Console.Write(element + " ");
            }
            Console.WriteLine();
        }
        
        public static void merge(int[] array, int start, int mid, int end) {
            int[] resultArray = new int[ITEMSIZE];
            int low = start;
            int high = mid + 1;
            int key = start;
 
            // 나눠서 비교해서 정렬
            while (low <= mid && high <= end) {
                if (array[low] < array[high]) {
                    resultArray[key] = array[low];
                    low++;
                } else {
                    resultArray[key] = array[high];
                    high++;
                }
                key++;
            }
            // 오른쪽(high) array 값이 다 처리 안됫을 경우
            if (low > mid) {
                for (high = high; high <= end; high++) {
                    resultArray[key] = array[high];
                    key++;
                }
            // 왼쪽(low) array 값이 다 처리 안됫을 경우
            }  else {
                for (low = low; low <= mid; low++) {
                    resultArray[key] = array[low];
                    key++;
                }
            }
            // 임시로 만든 array를 정렬할 array에 복사
            for (int i = start; i <= end; i++) {
                array[i] = resultArray[i];
            }
            printArray(array);
        }
        
        public static void mergeSort(int[] array, int start, int end) {
            if (start < end) {
                int mid = ((start + end) / 2);
                mergeSort(array, start, mid);
                mergeSort(array, mid + 1, end);
                merge(array, start, mid, end);
            }
        }
    }
}

출력 값은 다음과 같다.

제일 마지막 줄이 정렬 후 결과이며

첫번째 부터는 중간중간 진행 과정이다.