算法2.10 合并排序算法(MergeSort)

合并排序也用了分治的策略，不过划分只是从中间做，而merge复杂一些．

 

#include
#include
#include

#define MAX_LENGTH 100

/*Show usage*/
void usage(char * prog)
{
        printf("%s Usage:\n", prog);
        printf("%s (Both should be less than 100)>\n", prog);
}

/*Generate and initialize the list*/
int * generate_list(int count)
{
        int i;
        int * list;

        list = (int *)malloc(count*sizeof(int));
        if(list == NULL)
        {
                perror("malloc");
                return NULL;
        }

        /*Initialize the list with integers less than 100*/
        srandom((unsigned int)time(NULL));
        for (i  = 0; i < count ; i ++)
                list[i] = random()%100;

        return list;
}

/*Show the list*/
void show_list(int * list, int length)
{
        int i;
        for(i = 0; i < length; i ++)
                printf("%d      ", list[i]);

        printf("\n");
}

void merge(int * srclist, int first, int mid, int last)
{
        int * ord_list = (int *)malloc((last - first + 1)* sizeof(int));
        int i = first, j = mid+1, k = 0;
        int t;
        while((i <= mid) && (j <= last))
        {
                if(srclist[i] < srclist[j])
                {
                        ord_list[k] = srclist[i];
                        i ++;
                        k ++;
                }
                else
                {
                        ord_list[k] = srclist[j];
                        j ++;
                        k ++;
                }
        }

        if(i > mid)
        {
                for(t = j; t <= last; t ++)
                {
                        ord_list[k] = srclist[t];
                        k ++;
                }
        }
        else
        {
                for(t = i; t <= mid ; t ++)
                {
                        ord_list[k] = srclist[t];
                        k ++;
                }
        }

        t = first;
        while(t <= last)
        {
                srclist[t] = ord_list[t - first];
                t ++;
        }
        free(ord_list);
}

/*algorithm*/
void merge_sort(int * list, int first, int last)
{
        int middle;
        if(first < last)
        {
                middle = (first + last)/2;
                merge_sort(list, first, middle);
                merge_sort(list, middle +1, last);
                merge(list, first, middle, last);
        }
}

int main(int argc, char * argv[])
{
        int length;
        int * list = NULL;

        /*Deal with the arguments*/
        if(argc != 2)
        {
                usage(argv[0]);
                exit(127);
        }

        length = atoi(argv[1]);

        if(!length || length > MAX_LENGTH)
        {
                usage(argv[0]);
                exit(129);
        }

        list = generate_list(length);

        printf("Source List:\n");
        show_list(list, length);

        merge_sort(list, 0, length-1);

        printf("Ordered List:\n");
        show_list(list, length);

        free(list);
        return 1;
}