POJ_2299&Merge_Sort

/**Merge_Sort**/

#include
#include

typedef int RecType;    // elementType

void Merge(RecType *R,int low,int m,int high)
{
    int i=low,j=m+1,p=0;

    RecType *R1;
    R1=(RecType *)malloc((high-low+1)*sizeof(RecType));
    if(!R1)return;
    
    while(i<=m&&j<=high)
        R1[p++]=(R[i]<=R[j])?R[i++]:R[j++];
    while(i<=m)
        R1[p++]=R[i++];
    while(j<=high)
        R1[p++]=R[j++];
    for(p=0,i=low;i<=high;p++,i++)
        R[i]=R1[p];
    free(R1);
}

void MergeSort(RecType R[],int low,int high)
{
    int mid;
    if(low    {
        mid=(low+high)/2;
        MergeSort(R,low,mid);
        MergeSort(R,mid+1,high);
        Merge(R,low,mid,high);
    }
}

int main (int argc, char ** argv){
    if(argc != 2)
    {
        printf("Usage: [exec] + [num]\n");
        return 0;
    }
    int len = atoi(argv[1]);
    int R[len];
    int i = 0;
    printf("Input %d numbers:\n", len);
    while(i        scanf("%d", &R[i++]);
   
    MergeSort(R, 0, len-1);
   
    printf("After Sorting: R[] = \n");
    i = 0;
    while(i < len)
        printf("%d ", R[i++]);
    printf("\n");
}
/***************************************************************************************/
/***********
**POJ 2299**
***********/

#include
#include

long long num = 0;

void Merge(int *R,int low,int m,int high)
{
    int i=low,j=m+1,p=0;

    int *R1;
    R1=(int *)malloc((high-low+1)*sizeof(int));
    if(!R1)return;

    while(i<=m&&j<=high)
    {
        if(R[i] <= R[j])
            R1[p++] = R[i++];
        else
        {   
            R1[p++] = R[j++];
            num += m - i + 1;
        }
    }   

    while(i<=m)
        R1[p++]=R[i++];
    while(j<=high)
        R1[p++]=R[j++];
    for(p=0,i=low;i<=high;p++,i++)
        R[i]=R1[p];

    free(R1);
}

void MergeSort(int R[],int low,int high)
{
    int mid;
    if(low    {
        mid=(low+high)/2;
        MergeSort(R,low,mid);
        MergeSort(R,mid+1,high);
        Merge(R,low,mid,high);
    }
}

int main (){
    int len;
    while(scanf("%d",&len) && len!=0)
    {
        int R[len];
        int i = 0;
        num = 0;
        while(i            scanf("%d", &R[i++]);
        MergeSort(R, 0, len-1);
        printf("%lld\n",num);
    }
}