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


/* swap entries in array a at positions i and j; used by bubblesort */
void swap(int * a, int i, int j)
{
	int t = a[i];
	a[i] = a[j];
	a[j] = t;
}


/* (bubble) sort array a; array is of length n */
void bubblesort(int * a, int n)
{
	int i, j;
	for (i = n-2; i >= 0; i--)
		for (j = 0; j <= i; j++)
			if (a[j] > a[j+1])
				swap(a, j, j+1);
}


/* merge two sorted arrays a1, a2 of size n1, n2, respectively */
int * merge(int * a1, int n1, int * a2, int n2)
{
	int * result = (int *)malloc((n1 + n2) * sizeof(int));
	int i = 0,j=0,k;  
	for (k = 0; k < n1 + n2; k++) {
		if (i >= n1) {
			result[k] = a2[j];
			j++;
		}
		else if (j >= n2) {
			result[k] = a1[i];
			i++;
		}
		else if (a1[i] < a2[j]) { 
			result[k] = a1[i];
			i++;
		}
		else {
			result[k] = a2[j];
			j++;
		}
	}
	return result;
}


int main(int argc, char ** argv)
{
	int i,j;
	int n; // size of the array
	int *inArray; //input array

	int c, s; // elements to be sent in the message 
	int p, id; // p: number of processes in comunicator
	int rs; // size of receiving buffer
	int * sendBuffer;
	int * recBuffer;

	int step; //merge steps

	MPI_Status status;
	double elapsed_time;  


	MPI_Init(&argc, &argv);
	MPI_Comm_size(MPI_COMM_WORLD, &p);
	MPI_Comm_rank(MPI_COMM_WORLD, &id);

	if (id == 0) {
		// read size of inArray
		printf("Enter number of elements to be sorted");
		scanf("%d", &n);

		//allocating the size of array
		inArray = (int *)malloc(n*sizeof(int));

		//initiliazing array with random numbers
		for (j = 0 ; j < n ; j++)
		{	
			inArray[j]=rand()%100;
		}
		/*
		for (j = 0 ; j < n ; j++)
		{
		printf("%d \n",inArray[j]);
		}*/
		// compute Buffer size for the sending buffer
		c = n/p; if (n%p) c++;    
	}

	// start the timer
	MPI_Barrier(MPI_COMM_WORLD);
	elapsed_time = - MPI_Wtime();
	// broadcast size
	MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);

	// compute sendBuffer size
	c = n/p; if (n%p) c++;

	// scatter input Array(inArray)
	sendBuffer = (int *)malloc(c * sizeof(int));
	MPI_Scatter(inArray, c, MPI_INT, sendBuffer, c, MPI_INT, 0, MPI_COMM_WORLD);
	free(inArray);
	inArray = NULL;

	// compute size of sending buffer and sort it
	if(n >= c * (id+1)) s=c;
	else s= n - c * id;  
	//printf("s: %d",s);
	bubblesort(sendBuffer, s);

	// merge steps up to log p 
	for (step = 1; step < p; step = 2*step) {
		if (id % (2*step)!=0) {
			MPI_Send(sendBuffer, s, MPI_INT, id-step, 0, MPI_COMM_WORLD);
			break;
		}
		if (id+step < p) {
			// compute size of sendBuffer to be received
			rs = (n >= c * (id+2*step)) ? c * step : n - c * (id+step);
			// receive recBuffer sendBuffer
			recBuffer = (int *)malloc(rs * sizeof(int));
			MPI_Recv(recBuffer, rs, MPI_INT, id+step, 0, MPI_COMM_WORLD, &status);
			// merge and free memory
			inArray = merge(sendBuffer, s, recBuffer, rs);
			free(sendBuffer);
			free(recBuffer);
			sendBuffer = inArray;
			s = s + rs;
		}
	}  
	elapsed_time += MPI_Wtime();  

	if (id == 0) {	
		printf("\nSorted Array\n");
		for (i = 0; i < s; i++)
			printf("%d\n", sendBuffer[i]);   
		printf("Bubblesort %d ints on %d procs: %f secs\n", n, p, elapsed_time);    
	}
	MPI_Finalize();
	while(1);
	return 0;
}