상용 정렬 알고리즘 - 병합 정렬

병합 정렬의 원리:
배열의 요소 개수가 1보다 크면 다음을 수행합니다.
수조를 평균 두 부분으로 나누기;
왼쪽의 수조 병합 정렬;차례로 돌아가다
오른쪽의 수조 병합 정렬;차례로 돌아가다
두 개의 질서정연한 수조를 합병하려면 추가 보조 수조가 필요하며 합병 결과를 잠시 저장해야 한다.되돌아오다
그렇지 않으면 그룹 원소의 개수가 1일 때 이미 질서가 있다.바로 돌아갑니다.
 
정렬을 안정시키다.시간 복잡도는 최악, 최악, 평균 상황에서 모두 O(N lgN)이고 공간 복잡도는 O(N)이다.
 
코드:

 1 #include <iostream>

 2 using namespace std;  3 

 4 template<typename T>

 5 void mergeSortedArray(T src[], int first, int mid, int last, T tmp[])  6 {  7     int i = first, j = mid + 1;  8     int idx = 0;  9 

10     while(i <= mid && j <= last) 11  { 12         tmp[idx++] = src[i] < src[j] ? src[i++] : src[j++]; 13  } 14 

15     while(i <= mid) 16  { 17         tmp[idx++] = src[i++]; 18  } 19     while(j <= last) 20  { 21         tmp[idx++] = src[j++]; 22  } 23 

24     for(i = 0; i < idx; ++i) 25  { 26         src[first + i] = tmp[i]; 27  } 28 } 29 

30 template<typename T>

31 void mergeSort(T src[], int first, int last, T tmp[]) 32 { 33     if(first >= last) 34         return; 35 

36     int mid = first + ((last - first) >> 1);  // ，  37 

38     mergeSort(src, first,   mid,  tmp);       //  39     mergeSort(src, mid + 1, last, tmp); 40 

41     mergeSortedArray(src, first, mid, last, tmp);  // ，tmp ，  42 } 43 

44 int main() 45 { 46     const int n = 5; 47 

48     int    ia[n] = {1, 3, 6, 2, 4}; 49     int itmp[n]; 50     mergeSort(ia, 0, n - 1, itmp);  //sort

51     for(int i = 0; i < n; ++i) 52         cout << ia[i] << ' '; 53     cout << endl; 54 

55     double da[n] = {1.2, 3.4, 6.7, 2.3, 4.5}; 56     double dtmp[n]; 57     mergeSort(da, 0, n - 1, dtmp);  //sort

58     for(int i = 0; i < n; ++i) 59         cout << da[i] << ' '; 60     cout << endl;
61 return 0;
62 }