(병합그룹) 병합정렬(2 - way)

병합정렬은 

1. 같은 개수의 원소를 가지는 부분집합으로 기존 자료를 분할하고

2. 분할된 각 부분 집합을 병합하면서 정렬 작업을 완성하는 분할정복 기법에 의한 정렬방식이다.

즉, 여러개의 정렬된 부분집합을 결합하여 정렬된 집합을 만드는 알고리즘 이다.

2개의 정렬된 자료집합을 병합하면 2 - way 병합 / n개의 정렬된 자료 집합을 결합 n - way 병합

데이터는 80, 50, 70, 10, 60, 20, 40, 30의 8개의 정수 배열이다. 오름차순

병합 정렬은 먼저 기존 자료를 동일한 개수의 원소를 가지는 부분 집합으로 분할해야한다.

여기서는 2 - way 병합을 사용해야하니까 초기 전체 자료를 2개의 부분 집합으로 나눈다.

또한 나뉜 2개의 부분 집합에 대해서도 각각 2개의 부분 집합으로 나눈다. 이러한 분할 단계를 더 이상 나눌 수 없을 때까지 (1개겠지?) 계속하여

결국 아래 그림과 같이 모두 8개의 부분 집합으로 나눈다.

여기까지가 분할단계이다.

다음 병합단계는

2 - way 병합에서는 나누어진 2개의 부분 집합을 각각 병합하면서 정렬을 한다. 그럼 최종적으로 정렬이 완성된다.

2개의 부분 집합의 원소를 차례로 비교하면서 정렬이 된다. 

10, 50, 70, 80 // 20, 30, 40, 60

이렇게 병합하려는 2개의 부분 집합이 있다면..

첫 원소들을 비교하여 키 값이 작은 원소를 선택하게 된다. 10이 선택되었고 선택된 부분 집합의 경우 선택된 원소의 다음 원소를 가리키도록 한다.

다음 50과 20을 비교하고 20이 선택되고 20을 가리키던것은 30을 가리킨다.

두 부분 집합 중에서 어느한쪽이 선택이 모두 되었다면, 남은 부분 집합의 값들을 정렬된 집합의 뒤에 복사해버리면 된다.

C#

        void mergeSort(int[] value, int[] buffer, int start, int end)

        {

            int middle = 0;

            

            //원소의 개수가 1개가 될 떄까지 순환적으로 병합 정렬을 실행한다.

            if(start < end)

            {

                //2개의 부분 집합으로 나누기 위해 중간위치 middle을 구한다.

                middle = (start + end) / 2;

                //왼쪽 부분집합과 오른쪽 부분집합에 대해 순환적으로 병합정렬을 실행

                mergeSort(value, buffer, start, middle);

                mergeSort(value, buffer, middle + 1, end);

                mergeSortInternal(value, buffer, start, middle, end);

            }

        }

        void mergeSortInternal(int[] value, int[] buffer, int start, int middle, int end)

        {

            int i, j, k, t = 0;

            i = start;

            j = middle + 1;

            k = start;

            while(i <= middle && j <= end)

            {

                if(value[i] <= value[j])

                {

                    buffer[k] = value[i];

                    ++i;

                }

                else

                {

                    buffer[k] = value[j];

                    ++j;

                }

                ++k;

            }

            if(i > middle)

            {

                for (t = j; t <= end; ++t, ++k)

                    buffer[k] = value[t];

            }

            else

            {

                for (t = i; t <= middle; ++t, ++k)

                    buffer[k] = value[t];

            }

            for(t = start; t <= end; ++t)

            {

                value[t] = buffer[t];

            }

        }

병합정렬은 정렬도중에 배열의 개수만큼 추가 메모리 공간이 필요하다.

2 - way 병합 정렬은 이동 및 비교 연산이 평균적으로 O(nlogn)번 필요한 비교적 우수한 효율성을 가진다.

따라서 최선, 평균, 최악 모두 O(nlogn)이다. 매수 효율이 우수한 정렬방식이다.

단 위에서 말한 추가 메모리 공간이 필요함. 그리고 자료의 이동 횟수가 많아서 자료의 크기가 크다면 시간적 낭비가 심해진다.

이때는 배열 대신에 연결리스트를 사용하여 실제 자료의 이동대신 포인터만을 변경하는 방식으로 성능을 향상시켜야 한다. 

아울러 병합 정렬은 안정성이 유지되는 정렬방식이다.

---