归并排序

 1 void sort(int *nums, int l, int mid, int r){
 2     int *tmp, i, lsub, rsub, len;
 3 
 4     len = r-l+1;
 5     lsub = l;
 6     rsub = mid+1;
 7 
 8     tmp = malloc(sizeof(int) * len);
 9     for (i = 0; i<len; ++i) {
10         if (lsub > mid) {
11             tmp[i] = nums[rsub++];
12             continue;
13         }
14         if (rsub > r){
15             tmp[i] = nums[lsub++];
16             continue;
17         }
18         if (nums[rsub] > nums[lsub]) {
19             tmp[i] = nums[lsub++];
20             continue;
21         } else {
22             tmp[i] = nums[rsub++];
23             continue;
24         }
25     }
26     for(i=0; i<len; ){
27         nums[l++] = tmp[i++];
28     }
29 }
30 void mergeSort(int *nums, int numsSize, int l, int r){
31     if (l>=r){return;}
32     int mid;
33     mid = (l+r)/2;
34 
35     mergeSort(nums, numsSize, l, mid);
36     mergeSort(nums, numsSize, mid+1, r);
37     sort(nums, l, mid, r);
38 }
39 /**
40  * Note: The returned array must be malloced, assume caller calls free().
41  */
42 int* sortArray(int* nums, int numsSize, int* returnSize){
43     int l, r, mid;
44     int *returnNums;
45     returnNums = malloc(sizeof(int) * numsSize);
46     memcpy(returnNums, nums, sizeof(int) * numsSize);
47     mid = numsSize/2;
48     *returnSize = numsSize;
49     mergeSort(returnNums, numsSize, 0, numsSize-1);
50     return returnNums;
51 }