自底向上的归并排序算法

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

static void merge(int r[], int low, int mid, int high);
static void mergepass(int r[], int length, int n);
static void mergesort(int r[], int n);

#define N 10

int main(void)
{
        int r[N] = {2, 4, 1, 56, 33, 55, 55, 3, 28, 110};
        int i;

        printf("before sort:\n");
        for(i = 0; i < N; i++){
                printf("r[%d] = %d\n", i, r[i]);
        }

        mergesort(r, N);
        printf("\n");

        printf("after sort:\n");
        for(i = 0; i < N; i++){
                printf("r[%d] = %d\n", i, r[i]);
        }

        exit(0);
}

static void merge(int r[], int low, int mid, int high)//将r[low..mid]和r[mid+1..high]合并成一个有序的数组r[low..high]

{
        //int temp[high-low+1] = {-1};

        int* temp = NULL;
        int i, j, k, len;

        i = low;
        j = mid + 1;
        k = 0;

        len = high-low+1;
        temp = (int* )malloc(len * sizeof(int));
        while((i <= mid) && (j <= high)){
                if(r[i] <= r[j]){
                        *(temp+k) = r[i++];
                        k++;
                }
                else{
                        *(temp+k) = r[j++];
                        k++;
                }
        }

        while(i <= mid){
                *(temp+k) = r[i++];
                k++;
        }

        while(j <= high){
                *(temp+k) = r[j++];
                k++;
        }

        for(i = low, j = 0; i <= high; i++, j++){
                r[i] = *(temp+j);
        }
}//merge


static void mergepass(int r[], int length, int n)//n为数组r[]的长度

{
        int i;

        for(i = 0; i+2*length-1 < n; i = i+2*length){//将数组r[]划分成一个个length长度的小数组块

                merge(r, i, i+length-1, i+2*length-1);//对相邻的两个数组块r[i..i+length-1]和

                                                        //r[i+length..i+2*length-1]进行合并排序

        }

        if(i+length < n){//还有最后两个数组，其中后一个长度小于length

                merge(r, i, i+length-1, n);
        }//注意：若i≤n且i+length-1≥n时，则剩余一个数组轮空，无须归并

}


static void mergesort(int r[], int n)
{
        int length;

        for(length = 1; length < n; length *= 2){
                mergepass(r, length, n);
        }
}