本文共 1271 字，大约阅读时间需要 4 分钟。

首先时间复杂度上：

logn*n

在这个过程中，一共要合并logn次的有序数列，而获取一个有序数列的时间复杂度是n，在获取的过程中，因为其实数列的原始排列顺序会影响这个过程的时间复杂度。比如是只比较1次就可以（后面数列的第一个元素就比前面数列的最后一个元素要大），那么此时比较一次就可以了。还是说需要max（n,m）次才可以将后面数列中的一个元素排列好，那么第二个元素也有可能是需要比较这么多次数。但是在归并排序中，将这个过程看成是O（n），所以可以说，归并排序的时间复杂度跟数列的初始状态没有关系。

void merge(int arr[], int low, int mid, int high){    int i, k;    int *tmp = (int *)malloc((high-low+1)*sizeof(int));    //申请空间，使其大小为两个    int left_low = low;    int left_high = mid;    int right_low = mid + 1;    int right_high = high;    for(k=0; left_low<=left_high && right_low<=right_high; k++){  // 比较两个指针所指向的元素        if(arr[left_low]<=arr[right_low]){            tmp[k] = arr[left_low++];        }else{            tmp[k] = arr[right_low++];        }    }    if(left_low <= left_high){  //若第一个序列有剩余，直接复制出来粘到合并序列尾    //memcpy(tmp+k, arr+left_low, (left_high-left_low+l)*sizeof(int));    for(i=left_low;i<=left_high;i++)        tmp[k++] = arr[i];    }    if(right_low <= right_high){    //若第二个序列有剩余，直接复制出来粘到合并序列尾    //memcpy(tmp+k, arr+right_low, (right_high-right_low+1)*sizeof(int));        for(i=right_low; i<=right_high; i++)            tmp[k++] = arr[i];    }    for(i=0; i
   
    > 1);        merge_sort(arr, first, mid);        merge_sort(arr, mid+1,last);        merge(arr,first,mid,last);    }    return;}
   

转载地址：http://ywbab.baihongyu.com/