归并排序

/**

Description

2-归并排序对给出序列进行排序（升序），输出使用2-归并排序时关键字交换次数。

数据输入：

测试文件包含多测试用例, 第个测试用例以N(0 < N < 500,000 )开始, 接着有N个数,

最后一个测试用例为n=0, 不作处理.

数据输出：

对第个测试用例输出一行,仅包含2-归并排序时关键字交换次数.

Sample Input

5

9

1

0

5

4

3

1

2

3

0

Sample Output

6

0

*/

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


typedef struct node *pNode;

struct node
{
    __int64 data;
};

__int64 mergeSort(pNode source,pNode destination,__int64 begin,__int64 end);
__int64 merge(pNode source,pNode destination,__int64 begin,__int64 mid,__int64 end);
void printArray(pNode destination,__int64 n);

int main()
{
    __int64 n,i,result;//n表示输入的表示待排序的元素个数
    pNode source,destination,pTemp1,pTemp2;

    while(1 == scanf("%I64d",&n) && n != 0)
    {
        source = NULL;
        destination = NULL;

        source = (pNode)malloc(n * sizeof(__int64));
        destination = (pNode)malloc(n * sizeof(__int64));

        if(source == NULL || destination == NULL)
        {
            exit(1);
        }


        for(i=0; i<n; i++)
        {
            scanf("%I64d",&((source+i)->data));
        }

       // printArray(sourceArray,n);
        result = mergeSort(source,destination,0,n-1);

        //printArray(destination,n);
       // printArray(sourceArray,n);
        printf("%I64d\n",result);

        pTemp1 = source;
        pTemp2 = destination;
        free(pTemp1);
        free(pTemp2);
    }

    return 0;
}


__int64 mergeSort(pNode source,pNode destination,__int64 begin,__int64 end)
{
    __int64 mid,temp1 = 0,temp2 = 0,temp3 = 0;
    if(begin == end)
    {
        (destination+begin)->data = (source+end)->data;
    }
    else if(begin < end)
    {
        mid = (begin + end) / 2;
        temp1 = mergeSort(source,destination,begin,mid);
        temp2 = mergeSort(source,destination,mid+1,end);
        temp3 = merge(source,destination,begin,mid,end);
    }

    return temp1 + temp2 + temp3;
}


__int64 merge(pNode source,pNode destination,__int64 begin,__int64 mid,__int64 end)
{
    __int64 i = begin,j = mid + 1,k = begin,count = 0;
    while(i <= mid && j <= end)
    {
        if((source+i)->data <= (source+j)->data)
        {
            (destination+k)->data = (source+i)->data;
            i++;
            k++;
        }
        else
        {
            (destination+k)->data = (source+j)->data;
            //printf("%d,%d\n",sourceArray[i],sourceArray[j-1]);
            count += mid - i + 1;
            j++;
            k++;
        }
    }

    while(i <= mid)
    {
        (destination+k)->data = (source+i)->data;
        i++;
        k++;
    }

    while(j <= end)
    {
        (destination+k)->data = (source+j)->data;
        j++;
        k++;
    }

    i = begin;
    while(i <= end)
    {
        (source+i)->data = (destination+i)->data ;
        i++;
    }

    return count;
}


//打印数组

void printArray(pNode destination,__int64 n)
{
    __int64 i;

    for(i=0; i<n; i++)
    {
        printf("%I64d ",(destination+i)->data);
    }

    printf("\n");
}