归并排序

    归并排序：
    设归并排序的当前区间是R[low..high]，分治法的三个步骤是：
①分解：将当前区间一分为二，即求分裂点
                
②求解：递归地对两个子区间R[low..mid]和R[mid+1..high]进行归并排序；
③组合：将已排序的两个子区间R[low..mid]和R[mid+1..high]归并为一个有序的区间R[low..high]。
  递归的终结条件：子区间长度为1（一个记录自然有序）。

#include <stdio.h>
#include <limits.h>

void merge(int *a, int start, int mid, int end);
void mergeSort(int *a, int start, int end);

int
main(int argc, char **argv)
{
    int a[] = {2, 3, 4, 9, 8, 6, 0, 4, 1, 5, 7};
    int num;

    num = sizeof(a) / sizeof(int);

    printf("num = %d.\n", num);

    int i;

    printf("Before merge sort:\n");
    for(i = 0; i < num; i++) {
        printf("%d,", a[i]);
    }
    printf("\n");

    mergeSort(a, 0, num-1);

    printf("After merge sort:\n");
    for(i = 0; i < num; i++) {
        printf("%d,", a[i]);
    }
    printf("\n");

    return 0;
}

void merge(int *a, int start, int mid, int end)
{
    int n1, n2;

    n1 = mid - start + 1;
    n2 = end - mid;

    int L[n1 + 1], R[n2 + 1];

    int i, j;

    for(i = 0; i < n1; i++) {
        L[i] = *(a+start+i);
    }

    for(j = 0; j < n2; j++) {
        R[j] = *(a+mid+j+1);
    }

    L[i] = INT_MAX;
    R[j] = INT_MAX;

    i = j = 0;

    int t;
    for(t = start; t <= end; t++) {
        if(L[i] <= R[j]) {
            *(a+t) = L[i];
            i++;
        } else {
            *(a+t) = R[j];
            j++;
        }
    }
}


void mergeSort(int *a, int start, int end)
{
    int mid;
    if(start < end) {
        mid = (start + end) / 2;
        mergeSort(a, start, mid);
        mergeSort(a, mid+1, end);
        merge(a, start, mid, end);
    }
}

注：平均时间复杂度为：O(nlgn)， 稳定。