병합 정렬(Merge-Sort)

병합정렬(merge_Sort) 
 - O(n lng n)의 수행시간이 걸린다.
 - 분할 정복기법을 이용해 정렬한다. 

1.동작원리
 1-1. 처음 주어진 배열을 하나의 원소 단위로 분할 한다. 
 1-2. 분할된 원소에 대해 서로 쌍을 비교해 정렬 후 병합한다.

2.소스
 2-1. mergesort 함수

1. /*
2. 병합 정렬을 실행하는 함수
3. 정렬할 n개의 수열을 n/2개씩 두 개의 부분 수열로 분할하고
4. 병합 정렬을 이용해 재귀적으로 그 두 부분 수열을 정렬한다
5. 정렬된 두개의 부분 수열을 병합해 하나의 정렬된 수열을 만든다.
6. */
7. void mergesort(int *arr,int p, int r)
8. {
9.     int q = 0;
10.  
11.     if(p < r)
12.     {
13.         q = (p + r) / 2; // 수열을 두개로 나누기 위한 중간 값을 계산
14.         mergesort(arr,p,q);
15.         mergesort(arr,q+1,r);
16.         merge(arr,p,q,r);
17.     }
18. }

 2-2. merge 함수

1. /*
2. 나누어진 원소를 정렬하며 병합하는 함수
3. */
4. void merge(int *arr, int p, int q, int r)
5. {
6.     int n1 = q - p +1;
7.     int n2 = r - q;
8.  
9.     int* left =(int*)malloc(sizeof(int) * (n1+1));
10.     int* right =(int*)malloc(sizeof(int) * (n2+1));
11.  
12.     int i = 0;
13.     int j = 0;
14.     int k = 0;
15.  
16.     for(i = 0; i < n1; i++)
17.         left[i] = arr[p+i];
18.     for(j = 0; j < n2; j++)
19.         right[j] = arr[q+j+1];
20.    
21.     left[n1] = 9999; // 경계값을 설정
22.     right[n2] = 9999; // 경계값을 설정
23.  
24.     i = 0;
25.     j = 0;
26.  
27.     // left, right 두 배열의 원소를 앞에서부터 차례대로 비교하며 정렬된 값을 저장한다.
28.     for(k = p ; k <= r; k++)
29.     {
30.         if(left[i] <= right[j])
31.         {
32.             arr[k] = left[i];
33.             i ++;
34.         }
35.         else
36.         {
37.             arr[k] = right[j];
38.             j ++;
39.         }
40.     }  
41. }

3. 결과