#include <stdio.h>
#include <mpi.h>
#define N 1000

int main (int argc, char *argv[])
 {
  int myid, numprocs;
  int myFirst,myLast;
  int *a,*b;
  long iter=0;
  int i,j,tmp,tmp2;
  double start,end;
  MPI_Status status;

  MPI_Init(&argc, &argv);
  MPI_Comm_size(MPI_COMM_WORLD,&numprocs);
  MPI_Comm_rank(MPI_COMM_WORLD,&myid); 
  if (((N % numprocs) == 0) && (N >= (numprocs *2)))
   {
    a = (int *) malloc(N * sizeof(int));
    if (myid == 0)
     {
      // Fill array with unsorted integers
      for (i=0; i<N;i++) a[i]=rand();
      printf("Unsorted:\n");
      for (i=0; i<N; i++) printf("a[%d] = %d\n",i,a[i]);
      start = MPI_Wtime();
     } // if (myid == 0)
    MPI_Bcast(a,N,MPI_INT,0,MPI_COMM_WORLD);
    myFirst = (N/numprocs)*myid;
    myLast = (N/numprocs)*myid + (N/numprocs) - 1;
    for(i=0; i<N; i++)
     for(j=myLast; j>=myFirst; j--)
      {
       iter++;
       if (j == myFirst) 
        { 
         if (myid > 0) // send my first row to myid-1
          MPI_Send(&a[myFirst],1,MPI_INT,myid-1,0,MPI_COMM_WORLD);
         if (myid < (numprocs-1)) // recv myLast + 1
          MPI_Recv(&tmp2,1,MPI_INT,myid+1,0,MPI_COMM_WORLD,&status);
         if (a[myLast] > tmp2)
          {
           tmp = tmp2;
           tmp2 = a[myLast];
           a[myLast] = tmp;            
          }
         if (myid < (numprocs-1)) // send greater value to myid+1
          MPI_Send(&tmp2,1,MPI_INT,myid+1,0,MPI_COMM_WORLD);
         if (myid > 0) // recv myFirst from myid-1
          MPI_Recv(&a[myFirst],1,MPI_INT,myid-1,0,MPI_COMM_WORLD,&status);
        }
       else 
        {
         if (a[j-1] > a[j])
          {
           tmp = a[j];
           a[j] = a[j-1];
           a[j-1] = tmp;
          }
        }
      }
     if (myid == 0)
      {
       b = (int *) malloc(N * sizeof(int));
       for (i=1; i<numprocs; i++)
        { 
         MPI_Recv(b,N,MPI_INT,i,0,MPI_COMM_WORLD,&status);
         for (j=(N/numprocs)*i; j<(N/numprocs)*i + (N/numprocs); j++)
           a[j] = b[j];
         }
        end = MPI_Wtime();
        printf("\nSorted:\n");
        for (i=0;i<N;i++)  printf("a[%d] = %d\n",i,a[i]);
        printf("%ld iterations in %.6f seconds\n",iter,end-start);
      }
     else
      MPI_Send(a,N,MPI_INT,0,0,MPI_COMM_WORLD);
   } // if ((N % numprocs) == 0) 
  else
   if (myid == 0) 
    {
     if ((N % numprocs) != 0)
      printf("ERROR: array of %d elements must be evenly divisable by number of processes\n",N); 
     if (N < (numprocs *2))
      printf("ERROR: need at least 2 array per process\n",N); 
    }
  MPI_Finalize(); 
 } // main