1 #include
     
       2 #include
      
        3 #include
       
         4 void merge(int a[], int p, int q, int r); 5 void merge_sort(int a[], int p, int r); 6 int main() { 7     int a[10] = { 6,5, 4, 3, 1, 2, 0, 7,8,9}; 8     int i = 0; 9     /*用来测试merge函数的一个实例*10 11     int idxa = 0, idxb = 4, idxc = 9;12 13     printf("Please input 10 numbers to the array:");14 15     printf("Three indexes are %d, %d and %d.\nThe first subarray is:", idxa, idxb, idxc);16     for (i = idxa; i <= idxb; i++)17         printf(" %d", a[i]);18     printf("\nThe second subarray is:");19     for (i = idxb + 1; i <= idxc; i++)20         printf(" %d", a[i]);21     printf("\n");22 23     merge(a, idxa, idxb, idxc);24     printf("The merged array is:");25     for (i = idxa; i <= idxc; i++)26         printf(" %d", a[i]);27     printf("\n");28     getchar();29     *测试用例到此处结束*/30 31     merge_sort(a, 0, 9);32     printf("The sorted array is:");33     for (i = 0; i < 10; i++)34         printf(" %d", a[i]);35     printf("\n");36     getchar();37     return 0;38 }39 void merge_sort(int a[], int p, int r){40     int q = 0;41     if (p < r) {42         q = (p + r) / 2;    //由于整数精度限制，自动对q进行了下取整43         merge_sort(a, p, q);44         merge_sort(a, q + 1, r);45         merge(a, p, q, r);46     }47 }48 void merge(int a[], int p, int q, int r) {49     /*无聊的声明，用于循环等操作*/50     int i = 0, j = 0, k = 0;51     /*声明需要的存储空间来存放数据*/52     int n1 = q - p + 1;               //设置子数组A[p...q],    此时需要q-p+1的大小的数组53     int n2 = r - q;                   //设置子数组A[q+1...r],    此时需要r - (q+1) + 1的大小的数组54     /*令L[n1 + 1]和R[n2 + 1]成为新的数组，其中 +1 是为了放置哨兵牌（一个代表极值的数）*/55     int *left  = (int *)malloc(sizeof(int) * (n1 + 1));    //申请一段存放左侧数组数据的空间56     int *right = (int *)malloc(sizeof(int) * (n2 + 1));    //申请一段存放左侧数组数据的空间57     /*初始化Left 和 Right*/58     for (i = 0; i < n1; i++) {59         *(left + i) = a[p + i];60     }61     for (j = 0; j < n2; j++) {62         *(right + j) = a[q + j + 1];63     }64     *(left    + n1) = INT_MAX;        //将最后一个设置为哨兵牌,因为是从小到大排序，所以将哨兵牌设为整数最大值65     *(right + n2) = INT_MAX;66 67     i = 0;            //无聊的初始化无聊变量，用于循环68     j = 0;69     /*从Left和Right中选小的一个合并到一起*/70     for (k = p; k <= r; k++) {71         if (*(left + i) <= *(right + j)) {72             a[k] = *(left + i);73             i++;74         }75         else {76             a[k] = *(right + j);77             j++;78         }79     }80     free(left);81     free(right);82 }