大神的世界

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

#define MAX_SIZE 1000
#define LIST_SIZE 10

void mergeSort(int list[], int n);
void mergePass(int list1[], int list2[], int s, int n);
void merge(int list1[], int list2[], int l, int m, int r);

int main()
{
    srand(time(NULL));
    int list[LIST_SIZE];

    list[0] = 0;
    for(int i = 1; i<LIST_SIZE; i++)
        list[i] = rand()%100;

    printf("before:\n");
    for(int i = 0; i<LIST_SIZE; i++)
        printf("%d ", list[i]);

    mergeSort(list, LIST_SIZE-1);

    printf("\nafter:\n");
    for(int i = 0; i<LIST_SIZE; i++)
        printf("%d ", list[i]);

    return 0;
}

void mergeSort(int list[], int n)
{
    int  s = 1;
    int extra[MAX_SIZE];

    while(s < n){
        mergePass(list, extra, s, n);
        s *= 2;
        mergePass(extra, list, s, n);
        s *= 2;
    }
}

void mergePass(int list1[], int list2[], int s, int n)
{
    int i;
    for(i = 1; i<= n-2*s+1; i+=2*s)
        merge(list1, list2, i, i+s-1, i+2*s-1);

    if(i+s-1 < n)
        merge(list1, list2, i, i+s-1, n);
    else
        for(; i<=n; i++)
            list2[i] = list1[i];
}

void merge(int list1[], int list2[], int l, int m, int r)
{
    int i, j, k;
    i = l, j = m+1, k = l;

    while(i <= m && j <= r){
        if(list1[i] < list1[j])
            list2[k++] = list1[i++];
        else
            list2[k++] = list1[j++];
    }

    if(i > m)
        for(; j<=r; j++)
            list2[k++] = list1[j];
    else
        for(; i<=m; i++)
            list2[k++] = list1[i];
}