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


void print_list(int list[], int length, int total_number);
void oddeven_s(int A[], int n);
void Oddeven_sort(int length, int B[]);
int Compare(const int *a, const int *b);

/**********************************************************************/
main(int argc, char *argv[])
{
    int cpu_num; /* cpu 的數目 */
    int my_rank; /* 自己 cpu 的編號 */
    int i, j;
    int N=5, n=1;  /* 造 n=2^N 個亂數的數列 */
    int cpu_list_size; /* 每顆 cpu 裡分到的數列長度 */
    int list_length;
    int *local_list, *temp_list;
    float totaltime, temp;
    clock_t start_time, end_time;


/**** MPI 命令開始 ****/
    MPI_Status status;
    MPI_Init(&argc, &argv);
    MPI_Comm_size (MPI_COMM_WORLD, &cpu_num);
    MPI_Comm_rank (MPI_COMM_WORLD, &my_rank);


/**** 造亂數數列 ****/
    for (i = 0; i < N; i++)
        n = (long)n * 2;
    cpu_list_size = (n / cpu_num); /*   每棵 cpu 要分的數列長度   */

    local_list = malloc(n * sizeof(int));
    temp_list = malloc(n * sizeof(int));

    srand((time(NULL)+my_rank)*(my_rank+1));
    for (i = 0; i < cpu_list_size; i++)    /*   每棵 cpu 各自造 cpu_list_size 長度的數列   */
        local_list[i] = rand();            /*                                              */


/**** 印出亂數數列 ****/
/*
    if (my_rank == 0) 
        printf("%d random numbers:\n",n);
    print_list(local_list, cpu_list_size, n);
*/


    start_time=clock();
/**** 開始 odd-even merge sort ****/
    for (i=1, list_length = cpu_list_size ; i < cpu_num; i = i*2, list_length = list_length *2)
    {
        if ( (my_rank) % (2*i) == 0)
        {
            oddeven_s(local_list, list_length);
            for (j=0; j<list_length/2; j++)
                temp_list[j] = local_list[j];
            MPI_Send(local_list + list_length/2, list_length/2, MPI_INT, my_rank + i, 0, MPI_COMM_WORLD);
            MPI_Recv(temp_list + list_length/2, list_length/2, MPI_INT, my_rank + i, 0, MPI_COMM_WORLD, &status);
        }
        if ( (my_rank + i) % (2*i) == 0)
        {
            oddeven_s(local_list, list_length);
            for (j=0; j<list_length/2; j++)
                temp_list[list_length/2 + j] = local_list[list_length/2 + j];
            MPI_Recv(temp_list, list_length/2, MPI_INT, my_rank - i, 0, MPI_COMM_WORLD, &status);
            MPI_Send(local_list, list_length/2, MPI_INT, my_rank - i, 0, MPI_COMM_WORLD);
        }
        /*   上面兩個 if 是兩顆 cpu 一組, 各自把數列從中間對切成兩半, 前半段叫奇, 後半段叫偶    */
        /*   然後把奇的部份跟偶的部份各自收集到兩顆 cpu                                         */


        if ( (my_rank + i) % (2*i) == 0)
        {
            oddeven_s(temp_list, list_length);
            MPI_Send(temp_list, list_length, MPI_INT, my_rank - i, 0, MPI_COMM_WORLD);
            free(temp_list);
            free(local_list);
        }
        if ( (my_rank) % (2*i) == 0)
        {
            oddeven_s(temp_list, list_length);
            MPI_Recv(temp_list + list_length, list_length, MPI_INT, my_rank + i, 0, MPI_COMM_WORLD, &status);
            oddeven_s(temp_list + list_length/2, list_length);
            for (j=0; j<list_length *2; j++)
                local_list[j] = temp_list[j];
        }
        /*   上面的兩個 if 是先把自己 cpu 裡的數列 sort 一遍後仿造單 cpu 時的移位後 sort,   */
        /*   sort 完後全部丟到編號較小的 cpu 裡                                             */
    }
    end_time=clock();
    totaltime=(float) (end_time - start_time) / (CLK_TCK * 10000);


    /*   下面的 for 是在比較每棵 cpu 所花的時間裡最多的   */
    for (i=1; i<cpu_num; i++)
    {
        if (my_rank == i)
            MPI_Send(&totaltime, sizeof(float), MPI_FLOAT, 0, 0, MPI_COMM_WORLD);
        if (my_rank == 0)
        {
            MPI_Recv(&temp, sizeof(float), MPI_FLOAT, i, 0, MPI_COMM_WORLD, &status);
            if (totaltime < temp)
                totaltime = temp;
        }
    }



/**** 印出 sort 好的數列 ****/
    if (my_rank == 0)
    {
        printf("\nSorte complete, %d random numbers spend %f seconds. \n", n, totaltime);
        for (i = 0; i < n; i++)
        {
            printf("%-5d   ",local_list[i]);
            if (i % 10 == 9)
                printf("\n");
        }
        printf("\n\n");
    }


    free(temp_list);
    free(local_list);

    MPI_Finalize(); 
/**** MPI END ****/
}




/*******************************************************************/
int Compare(const int *left, const int *right)
{
    if (*left < *right)
       return -1;
    else if (*left == *right)
       return 0;
    else
       return 1;
}



/*******************************************************************/
/* 印出全部數列的function */
void print_list(int list[], int length, int total_number)
{
    int i, j;
    int my_rank;
    int cpu_num;
    int *temp_list, *global_list;

    MPI_Status status;
    MPI_Comm_rank (MPI_COMM_WORLD, &my_rank);
    MPI_Comm_size (MPI_COMM_WORLD, &cpu_num);

    temp_list = malloc (total_number * sizeof(int));
    global_list = malloc (total_number * sizeof(int));


    if (my_rank != 0)
        MPI_Send(list, length, MPI_INT, 0, 0, MPI_COMM_WORLD);
    if (my_rank == 0) 
    {
        for (i = 1; i < cpu_num; i++)
        {
            MPI_Recv(temp_list, length, MPI_INT, i, 0, MPI_COMM_WORLD, &status);
            for (j = 0; j < length; j++)
                global_list[(i * (length)) + j] = temp_list[j];
        }
        for (j = 0; j < length; j++)
            global_list[j] = list[j];
    }

    if (my_rank == 0)
    {
        printf("\nRandom series: \n");
        for (i = 0; i < total_number; i++)
        {
            printf("%-5d   ", global_list[i]);
            if (i % 10 == 9)
                printf("\n");
        }
        printf("\n\n");
    }
}

/*********************************************************************/
/* odd-even merge sort 單cpu時的程式 */
void oddeven_s(int A[], int n)
{
    int list_length;
    int i;
    int start_index;


    for (list_length = 2; list_length <= n; list_length = list_length*2)
                for (start_index = 0; start_index < n; start_index = start_index + list_length)
                        Oddeven_sort(list_length, A + start_index);
}


/*********************************************************************/
/* odd-even merge sort 單 cpu時的副程式 */
void Oddeven_sort(int length, int B[])
{
    int i;
    int half_way;
    int *temp;


    temp = malloc(length*sizeof(int));
    for (i=0; i<length; i++)
                temp[i]=B[i];

   half_way = length/2;

    if (length > 4)
    {
                Oddeven_sort(half_way, B);
                Oddeven_sort(half_way, B + half_way);
    }


    for (i = 0; i < half_way; i=i+2)
                if (B[i] < B[half_way + i])
                {
                        temp[i]=B[i];
                        temp[i+1]=B[half_way + i];
                }
                else
                {
                        temp[i]=B[half_way + i];
                        temp[i+1]=B[i];
                }

    for (i = 1; i < half_way; i=i+2)
                if (B[i] < B[half_way + i])
                {
                        temp[half_way + i-1]=B[i];
                        temp[half_way + i]=B[half_way + i];
                }
                else
                {
                        temp[half_way + i-1]=B[half_way + i];
                        temp[half_way + i]=B[i];
                }
    for (i=0; i<length; i++)
        B[i]=temp[i];


    if (length > 4)
    {
                Oddeven_sort(half_way, B);
                Oddeven_sort(half_way, B + half_way);
    }

    for (i=0; i<length; i++)
                temp[i]=B[i];



    for (i=0; i < half_way-1; i++)
                if (temp[i+1] < temp[half_way + i])
                {
                        B[2*i+1]=temp[i+1];
                        B[2*i+2]=temp[half_way + i];
                }
                else
                {
                        B[2*i+1]=temp[half_way + i];
                        B[2*i+2]=temp[i + 1];
                }

    free(temp);
}