Merge Sort

병합정렬

• 분할정복 알고리즘의 대표적인 알고리즘
• 정렬할 데이터의 집합을 더이상 쪼갤 수 없을 때 까지 반으로 쪼개고 다시 정렬하면서 병합하면 된다.

알고리즘 동작 과정

• 정렬된 두 집합을 다시 병합하면서 정렬하는 알고리즘이다. 전체 데이터 집합을 정렬된 두 데이터 집합상태로 나누기 위해 데이터집합을 계속 반으로 나눈다. 계속 반으로 나누면서 2개의 데이터 집합이 각각 하나가 되면 분할은 종료하면 되는데 이유는 하나의 집합은 더이상 쪼갤 수 없을 뿐아니라 정렬된 상태로 볼 수 있기 때문이다.

1. 정렬할 데이터 집합을 반으로 나눕니다.
2. 나누어진 하위 데이터 집합의 크기가 2이상이면 이 하위 데이터 집합에 대해 1을 반복합니다.
3. 원래 같은 집합에서 나뉘어져 나온 하위 데이터 집ㅎ바 둘을 병합하여 하나의 데이터 집합으로 만듭니다. 단, 병합할 때 데이터 집합의 원소는 순서에 맞춰 정렬합니다.
   1. 두 데이터 집합을 합한 것만큼의 비어 있는 데이터 집합을 마련합니다.
   2. 두 데이터 집합의 첫 번째 요소들을 비교하여 작은 요소를 새 데이터 집합에 추가합니다. 그리고 새 데이터 집합에 추가된 요소는 원래의 데이터 지합에서 삭제합니다.
   3. 양쪽 데이터 집합이 빌 때까지 2과정을 반복합니다.
4. 데이터 집합이 다시 하나가 될 때 까지 3을 반복합니다.

알고리즘 구현 방법

• 이진트리 후위순회 깊이우선탐색으로 구현했다.

• data의 시작구간(left)와 마지막 구간(right)을 인덱스로 받는 mergeSrot함수로 left와 right의 중간인 mid값을 기준으로 계속 구간을 나누면서 함수에서 지정된 구간의 데이터의 하나가 될때 까지 깊이우선탐색을 진행한다.(왼쪽 자식노드의 구간은 left부터 mid까지, 오른쪽 자식노드의 구간은 mid+1부터 right까지)

• 왼쪽 자식노드와 오른쪽 자식노드의 함수가 리턴되면 본격적으로 부모노드의 병합정렬부분이 실행되는데, 왼쪽 자식노드의 구간과 오른쪽 자식노드의 구간 각각은 정렬된 상태이고 이 정렬된 두 데이터집합을 다시 정렬하면 된다.. (마지막 잎노드에서 왼쪽 자식노드, 오른쪽 자식노드의 각각의 구간의 데이터가 하니씩일때도 성립한다. 하나의 데이터는 정렬된 상태로 볼 수 있기 때문)

#include<stdio.h>
int data[10];
int temp[10];
void mergeSort(int left,int right) {
    int mid;
    if (left < right) {
        mid = (left + right)/2;
        mergeSort(left, mid);
        mergeSort(mid+1, right);
        //자식노드(함수)들의 리턴이 완료되어야 수행되는 곳=>후위순회

        //자식노드에서 정렬된 두 배열을 병합하면서 정렬
        int p1= left, p2 = mid + 1,p3=left;
        while (p1 <= mid && p2<= right) {
            if (data[p1] < data[p2])
                temp[p3++] = data[p1++];
            else 
                temp[p3++] = data[p2++];
        }
        //남는 원소 담는 코드
        while(p1<=mid)
            temp[p3++] = data[p1++];
        while(p2<=right)
            temp[p3++] = data[p2++];

        for (int i = left; i <= right; ++i) {
            data[i] = temp[i];
        }

    }
    else {

    }

}
int main() {
    freopen("input.txt", "rt", stdin);
    int n;

    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &data[i]);
    }
    mergeSort(0, n - 1);
    for (int i = 0; i < n; ++i) {
        printf("%d ", data[i]);
    }

    return 0;
}

병합정렬의 시간복잡도

• 크기가 N인 데이터를 1이 될 때 까지 반으로 분할하는 깊이는 logN이다.
• 각 깊이에 대해서 총 원소 N개를 N번 읽어오는 과정을 거치므로 NlogN의 시간복잡도를 가진다.

-------------------------------------------------------------------------------------------------------------

출처 : 뇌를 자극하는 알고리즘(박상현 저, 한빛미디어)