归并排序

一、原理：

如下图：对于一个序列：16, 7, 13, 10, ..., 14，我们先把16, 7归并且排序成新序列(7, 16)，把13, 10归并且排序成(10, 13), ..., 接着重复把(7, 16), (10, 13)归并且排序为(7, 10, 13, 16), 把(9, 15), (2, 3)归并且排序为(2, 3, 9, 15)...直到变成原来的序列，此时的序列也就排好序了。

二、代码：

 1 /*Sample Input:
 2   5
 3   -1 5 3 8 9
 4   6
 5   0 3 12 4 6 7
 6 
 7   Sample Output:
 8   -1 3 5 8 9
 9   0 3 4 6 7 12
10 */
11 
12 #include<bits/stdc++.h>
13 #define MAX  2147483647
14 using namespace std;
15 
16 void merge(int* arr, int left, int right){//对闭区间[left, right]进行归并，即left和right都能取到 
17     int mid = (left + right) / 2 + 1;
18     int arr1[mid - left + 1] ;
19     int arr2[right - mid + 2];
20     
21     for(int i = 0, k = left; k < mid; k++, i++) arr1[i] = arr[k]; 
22     arr1[mid - left] = MAX;
23     for(int i = 0, k = mid; k <= right; k++, i++)arr2[i] = arr[k]; 
24     arr2[right - mid + 1] = MAX;
25     
26     int i = 0;
27     int j = 0;
28     for(int k = left; k <= right; k++){
29         if(arr1[i] < arr2[j]){
30             arr[k] = arr1[i];
31             i++;
32         }
33         else{
34             arr[k] = arr2[j];
35             j++;
36         }
37     }
38     
39 }
40 void mergeSort(int *arr, int left, int right){//递归归并 
41     if(left < right){
42         int mid = (left + right) / 2 + 1;
43         mergeSort(arr, left, mid - 1);
44         mergeSort(arr, mid, right);
45         
46         merge(arr, left, right);
47     }
48 }
49 int main(){
50     int t;
51     while(cin >> t && t){
52         int arr[t];
53         for(int i = 0; i < t; i++)cin >> arr[i];
54         mergeSort(arr,0, t-1);
55         for(int i = 0; i < t; i++)cout << arr[i] << ' ';
56         cout << endl;
57     }
58 }

三、分析：

如下图，我们可以假设输入的长度为2^n，则生成的递归数高度为lg(n)，而每层的合并的复杂度为O(n)，所以归并排序的时间复杂度为O(nlgn)。

　　//End