数据结构与算法之归并排序

　　将若干个有序序列进行两两合并，直到所有待排记录都在一个有序序列为止。

1、二路归并排序

　　对于任意一个给定长度为n的待排序列，其中的n个记录各自为一个有序序列（单个记录必定是有序的），然后把相邻的两个序列归并，组成一个新的有序序列，一次下去，直到归并成一个有序序列为止。

把两个有序序列归并，数组arr归并前的序列，把归并后的有序序列放入数组arr1中。begin为第一个有序序列的第一个记录下标，middle为第一个有序序列的最后一个记录下标，middle+1为第二个有序序列的第一个记录下标，end为第二个有序序列的最后一个记录下标。

void _mergeSort(int arr[],int arr1[],int begin,int middle,int end){
    int i = begin,j=middle+1,k=begin;
    
    while(i<=middle && j<=end){
        if(arr[i]<=arr[j]) 
          arr1[k++] = arr[i++];
        else
          arr1[k++] = arr[j++];
    }
      while(i<=middle)
        arr1[k++] = arr[i++];
      while(j<=end)
        arr1[k++] = arr[j++];
}

将待排序序列分成若干个序列，待排序序列是数组arr中从下标begin开始到end结束的一段序列，通过归并后的有序序列是存放在数组arr1中，所以通过memcpy把arr1中begin开始到end结束的序列复制到数组arr中。

void mergeSort(int arr[],int arr1[],int begin,int end){
    int middle;
    int i;
    if(begin == end)
      arr1[begin] = arr[begin];
    else{
        middle = (begin + end)/2;
        mergeSort(arr,arr1,begin,middle);
        mergeSort(arr,arr1,middle+1,end);
        _mergeSort(arr,arr1,begin,middle,end);
        memcpy(&arr[begin],&arr1[begin],(end-begin+1)*sizeof(int));  
    }
}

测试

int main(){
    int i;
    int arr[10] = {45,7,8,34,64,22,767,32,823,40};
    int *arr1 = (int*)malloc(sizeof(arr));
    mergeSort(arr,arr1,0,9);

    for(i=0;i<10;i++)
        printf("%d ",arr[i]);

    free(arr1);
    return 0;
}

2、总结

时间复杂度：o(nlog2n)，是一种稳定的排序。

空间复杂度o(n)，在存储的过程中需要提供一个与原序列相同的存储空间。