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

void Make_numbers(long int [], int, int, int);
void Sequential_sort(long int [], int);
int Get_minpos(long int [], int);

main(int argc, char* argv[]) {

  long int *big_array, *local_array;
  long int number;
  int n=80, n_bar, p, my_rank, i;
  double start, stop;

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

  n = atoi(argv[1]);

  if (my_rank == 0) {
    start = MPI_Wtime();

    // Checar se os parametros são válidos
    if (n%p != 0) {
      fprintf(stderr,"The number of processes must evenly divide total elements.\n");
      MPI_Abort( MPI_COMM_WORLD, 2 );
      exit(1);
    }

    /* make big array */
    big_array = malloc(n*sizeof(long int));
    if (big_array==NULL) {
      fprintf(stderr, "Big_array malloc failed!!\n");
      MPI_Abort( MPI_COMM_WORLD, 3 );
      exit(0);
    }
    Make_numbers(big_array, n, n/p, p);
  }

  n_bar = n/p;

  local_array = malloc(n_bar*sizeof(long int));
  if (local_array==NULL) {
    fprintf(stderr, "local_array malloc failed!!\n");
    MPI_Abort( MPI_COMM_WORLD, 4 );
    exit(0);
  }

  /* Can use scatter if numbers are grouped in the big_array  */
  MPI_Scatter(big_array,   n_bar, MPI_LONG, local_array, n_bar, MPI_LONG, 0, MPI_COMM_WORLD);

  Sequential_sort(local_array, n_bar);

  MPI_Gather(local_array, n_bar, MPI_LONG, big_array,   n_bar, MPI_LONG, 0, MPI_COMM_WORLD);

  stop = MPI_Wtime();

  if (my_rank==0) {
    for(i=0; i<n; i++) printf("%7ld %c", big_array[i],
      i%8==7 ? '\n'  : ' ');
    printf("\n\nTime to sort using %d processes = %lf msecs\n",
     p, (stop - start)/0.001);
  }

  free(local_array);
  if (my_rank==0)
    free(big_array);
  MPI_Finalize();

}

void Make_numbers(long int big_array[], int n, int n_bar, int p) {

  int i, q;
  MPI_Status status;

  for (q = 0; q < p; q++) {
    for (i = 0; i < n_bar; i++) {
      big_array[q*n_bar+i] =  random() % (2*n/p) + (q*2*n/p);
    }
  }

}

void Sequential_sort(long int array[], int size) {
  /* Use selection sort to sort a list from smallest to largest */
  int      eff_size, minpos;
  long int temp;

  for(eff_size = size; eff_size > 1; eff_size--) {
    minpos = Get_minpos(array, eff_size);
    temp = array[minpos];
    array[minpos] = array[eff_size-1];
    array[eff_size-1] = temp;
  }
}

/* Return the index of the smallest element left */
int Get_minpos(long int array[], int eff_size)
{
  int i, minpos = 0;

  for (i=0; i<eff_size; i++)
    minpos = array[i] > array[minpos] ? i: minpos;
  return minpos;
}