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

void Oddeven_sort(int length, int B[]);

/*********************************************************************/
main()
{
    int list_length;
    int i;
    int N=15, n=1;  /* 计 2^N */
    int start_index;
    int *A;
    float ttime;
    clock_t start_time, end_time;



    for (i = 0; i < N; i++)        
		n = (long)n * 2;   

    A = malloc(n * sizeof(int));

    srand(time(NULL));
    for (i=0; i<n; i++)           /*   硑睹计计   */
		A[i]=rand();      /*                */


    for (i=0; i<n; i++)           /*                  */
    	printf("%-5d   ",A[i]);   /*   睹计计   */
    printf("\n\nSorting...\n");   /*                  */


    start_time=clock();
    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);


    end_time=clock();
    ttime=(long)(end_time-start_time)/(CLK_TCK * 10000);
    printf("\nSort Complete, %d numbers spend %f seconds.\n", n,ttime);

    for (i=0; i<n; i++)                    /*    sort 计   */
		printf("%-5d   ",A[i]);    /*                      */

    printf("\n");
    free(A);

}



/*********************************************************************/
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];
		}
/*   计蛤案计竒だㄓ碞琌 sort   */

    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];


/*   计案计计常 sort 挡ㄓ琌рㄢ计簿ゑ merge   */
    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];
		}
/*   簿ゑ挡计蛤案计场 merge Ч拨   */

    free(temp);
}