정렬 알고리즘 - 병합 정렬 (merge)

병합 정렬은 귀속과 분할을 치료하는 기술을 이용하여 데이터 서열을 점점 작은 반자 표로 나누고 반자 표에 대해 정렬한다. 마지막으로 귀속 절차로 정렬된 반자 표를 병합하여 점점 더 큰 질서 서열로 만든다. 병합 정렬은 두 가지 절차를 포함한다. 각각 다음과 같다.
1) 분자계 2) 반자계 합병
시간 복잡도Θ(nlgn), 정렬 알고리즘을 삽입하는 것보다 낫다.
 
알고리즘 설명
1) 정렬된 두 개의 서열의 합으로 크기를 조정할 수 있는 요청 공간
2) 두 개의 포인터를 설정합니다. 첫 번째 위치는 정렬된 두 시퀀스의 시작 위치입니다.
3) 두 포인터가 가리키는 요소를 비교하여 상대적으로 작은 요소를 병합 공간에 넣고 포인터를 다음 위치로 이동합니다.
4) 포인터가 시퀀스 끝에 도달할 때까지 3단계 반복
5) 다른 시퀀스에 남은 모든 요소를 병합 시퀀스 끝으로 직접 복사
특징: 병합 정렬은 안정적인 정렬이다.즉, 같은 원소의 순서는 바뀌지 않고 속도는 빠른 정렬에 버금가지만 안정적이다.
 
알고리즘 구현:

 1 //merge-sort

 2 void merge(int *arry,const int first,const int mid,const int last)

 3 {

 4     int i,index;

 5     int first1,last1;

 6     int first2,last2;

 7     int *tmp;

 8     tmp=(int*)malloc((last-first+1)*sizeof(int));

 9     if (tmp==NULL)

10         return ;

11     first1=first;

12     last1=mid;

13     first2=mid+1;

14     last2=last;

15     index=0;

16     while((first1<=last1)&&(first2<=last2))

17     {

18         if (arry[first1]<arry[first2])

19         {

20             tmp[index++]=arry[first1];

21             first1++;

22         }

23         else{

24             tmp[index++]=arry[first2];

25             first2++;

26         }

27     }

28     while(first1<=last1)

29     {

30         tmp[index++]=arry[first1++];

31     }

32     while(first2<=last2)

33     {

34         tmp[index++]=arry[first2++];

35     }

36     for (i=0;i<last-first+1;i++)

37     {

38         arry[first+i]=tmp[i];

39     }

40     free(tmp);

41 }

42 

43 /* */

44 void merge_sort(int *arry,const int first,const int last)

45 {

46     int mid=0;

47     if (first<last)

48     {

49         mid=(first+last)/2;

50         merge_sort(arry,first,mid);

51         merge_sort(arry,mid+1,last);

52         merge(arry,first,mid,last);

53     }

54 }

별도: 실현 방식은 교체 방식으로 실현한다(개인적인 느낌은 코드가 예뻐야 한다)

 1 /***   ***/

 2 void merge_sort(int *list, const int first, const int last)

 3 {

 4     int len= last-first+1;

 5     int left_min,left_max;

 6     int right_min,right_max;

 7     int index;

 8     int i;

 9     int *tmp;

10     tmp = (int *)malloc(sizeof(int)*len);

11     if( tmp == NULL || len <= 0 )

12         return;

13     

14     for( i = 1; i < len; i *= 2 )

15     {

16         for( left_min = 0; left_min < len - i; left_min = right_max)

17         {

18             int j;

19             right_min = left_max = left_min + i;

20             right_max = left_max + i;

21             j = left_min;

22             if ( right_max > len )

23                 right_max = len;

24             index = 0;

25             while( left_min < left_max && right_min < right_max )

26             {

27                 tmp[index++] = (list[left_min] > list[right_min] ? list[right_min++] : list[left_min++]);

28             }

29             while( left_min < left_max )

30             {

31                 list[--right_min] = list[--left_max];

32             }

33             while( index > 0 )

34             {

35                 list[--right_min] = tmp[--index];

36             }

37             display_array(j,i*2,list+j);

38         }

39     }

40     free(tmp);

41 }

테스트 호출 실례

 1 int main()

 2 {

 3     int arry[]={1,2,5,6,4,7};

 4     merge_sort(arry,0,5);

 5     for (int i=0;i<6;i++)

 6     {

 7         cout<<arry[i]<<" ";

 8     }

 9     system("pause");

10     return 0;

11 }

블로그 참조:http://blog.chinaunix.net/uid-24467128-id-2606195.html
　　　　　 http://www.cnblogs.com/jillzhang/archive/2007/09/16/894936.html