2018-02-08归并排序学习即思考

最终完成代码：

void merge(int *a, int l, int m, int r) {
    int start1 = l;
    int end1 = m;
    int start2 = m + 1;
    int end2 = r;
    int k,i;
    k = 0;

    int *temp = (int*)malloc((r - l + 1) * sizeof(int));

    while (start1 <= end1 && start2 <= end2) {
        if (a[start1] < a[start2]) {
            temp[k++] = a[start1++];
        }
        else {
            temp[k++] = a[start2++];
        }
    }
    while (start1 <= end1) {
        temp[k++] = a[start1++];
    }
    while (start2 <= end2) {
        temp[k++] = a[start2++];
    }

    for (i = 0; i < (r - l + 1); i++) {
        a[l + i] = temp[i];
    }
    free(temp);
}

void merge_sort(int *a,int l, int r){
    int m = (l + r) / 2;
    if(l < r){
        merge_sort(a,l,m);
        merge_sort(a,m+1,r);
        merge(a,l,m,r);
    }
}

学习总结：
第一个归并函数是将两个有序数组归并的函数，是通过两两对比分别插入到新数组的过程，因此他需要申请一个和原量数组空间和大小的空间来存放归并后的数组，由于该归并函数是用于归并排序的，所以其中有一个比较重要的操作，就是将归并之后的temp数组在复制给原数组，这样就可以在归并排序这个函数递归调用的时候确保每次调用的两个数组是有序的，其中归并排序这个递归函数采用的是分治法，在不满足条件left <right的情况下，只有可能是只有一个单一元素的数组，因为只有一个元素，因此该数组一定是有序的，之后就是通过两两归并，最终实现最后的排序。

空间及时间复杂度：
空间：O(n)
时间：O(nlogn)

时间复杂度图解分析

计算递归式表示的总代价，我们只要把各层代价加起来，递归树具有lgn+1层，每层的代价均为cn，所以总代价为cn(lgn+1) = cnlgn+cn,即O(nlogn)

稳定与否：稳定

归并排序图解原理