merge sort()程序：

和heapsort排序比起来。
时间度：那个cita打印不出来
T(n) = cita(1) if n =1
T(n) = 2T(n/2) + cita(n) if n> 1.
根据公式
可得：
                  T(n) = cita(n lg n)
[code]
  1 /* This is the main.c
  2  *
  3  */
  4 #include
  5 int B[6];
  6
  7 int main()
  8 {
  9         int t;
 10         printf("Input the number :\n");
 11         for(t = 1; t < 6; t++)
 12                 scanf("%d",&B[t]);
 13         Merge_partition(B, 1, 5);
 14         for (t = 1; t < 6; t++)
 15                 printf("%d\n",B[t]);
 16 }
 17
[/code]
[code]
/*This file declares the merge-function
 *
*/
#ifdef MERGE_H
#define MERGE_H
#endif

void Merge(int A[], int s, int m, int e);
void Merge_partition(int B[], int st, int en);
[/code]
/* The file define the merge function
 *
*/
#include"merge.h"

#include
#define MAX 99999999
#define oss_free(x) if(NULL !=(x))\
                  free(x)

void Merge_partition(int A[], int st, int en)
{
    if(st < en){
        int q = (st + en) / 2;
        Merge_partition(A, st, q);
        Merge_partition(A, q + 1, en);
        Merge(A, st, q, en);
    }
}

void Merge(int C[], int s, int m, int e)
{
    int fn = m - s + 1; /*This is the number of elements*/
    int ln = e - m;   /* same as above*/
   
    int *arrayfn = (int *)malloc((fn + 1) * sizeof(int));
    int *arrayln = (int *)malloc((ln + 1) * sizeof(int));
   
    int i, j;
    for(i = 0; i < fn; i++)
        *(arrayfn + i) = C[s + i];
    for(j = 0; j < ln; j++)
        *(arrayln + j) = C[m + j + 1];
   
    *(arrayfn + i) = MAX;
    *(arrayln + j) = MAX;

    i = 0;
    j = 0;
    int n;
    for(n = s; n <= e; n ++){
        if(*(arrayfn + i) <= *(arrayln + j)){
                C[n] = *(arrayfn + i);
                i++;
        }
        else{
            C[n] = *(arrayln + j);
            j++;
        }
    }

        oss_free(arrayfn);
        oss_free(arrayln);
}
[/code]
[code]
/*This file declares the merge-function
 *
*/
#ifdef MERGE_H
#define MERGE_H
#endif

void Merge(int A[], int s, int m, int e);
void Merge_partition(int B[], int st, int en);
[/code]
[code]
object = main.o merge.o
merge : $(object)
    cc -g -o merge $(object)
main.o :
    cc -g -c main.c
merge.o :
    cc -g -c merge.c
.PHONY : clean
clean    :
    rm merge $(object)
[/code]