merge sort--归并排序--分治

#include <stdio.h>
#include <stdlib.h>

#define MAX 5

void mergesort(int *);
void msort(int *, unsigned, unsigned);
void merge(int *, unsigned, unsigned,unsigned);
void showarray(int *);

void main()
{
    int array[MAX] = {5,3,4,2,1};

    showarray(array);
    mergesort(array);
    showarray(array);
}

void mergesort(int *p)
{
    msort(p,0,MAX-1);
}

void msort(int *p, unsigned first, unsigned last)
{
    unsigned mid;
    if(first < last) {
        mid = (first+last) / 2;
        msort(p,first,mid);
        msort(p,mid+1,last);
        merge(p,first,mid,last);
    }
}

void merge(int *p, unsigned first, unsigned mid, unsigned last)
{
    int i,j,k;
    int *q = (int *)malloc((last-first+1) * sizeof(int));

    i = first;
    j = mid+1;

    for(k = 0; i <= mid && j <= last; k++) {
        if(p[i] < p[j])    q[k] = p[i++];
        else q[k] = p[j++];
    }

    while(i <= mid) {
        q[k] = p[i++];
        k++;
    }
    while(j <= last) {
        q[k] = p[j++];
        k++;
    }
    for(i = 0, k = first; k <= last; k++) {
        p[k] = q[i];
        i++;
    }
    free(q);
}

void showarray(int *p)
{
    int i;
    for(i = 0; i < MAX; i++) {
        printf("%d ",p[i]);
    }
    printf("\n");
}

复杂度：T（n）=2*T（n/2）+cn    T(n)=cn*lgn+cn