executar_comandos

executar paralelo: mpicc -pg mergesort_paralelo.c -o mergesortparalelo && mpirun.openmpi -np 8 ./mergesortparalelo 
executar sequencial:  gcc -pg mergesort_sequencial.c -o mergesortsequencial && ./mergesortsequencial

pegar tempo paralelo: gprof -b mergesortparalelo gmon.out | more 
pegar tempo sequencial: gprof -b mergesortsequencial gmon.out | more

merge_sort_paralelo.c

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

#define MAX_LINHAS_DEBUG    20
#define TAM                 600000

int contador = 0;
int v[TAM];
int tp_inicial, tp_final;

int RandomInteger (int low, int high)
{
    int k;
    double d;
    d = (double) rand () / ((double) RAND_MAX + 1);
    k = d * (high - low + 1);
    return low + k;
}

void gera_vetor(int v[], int tamanho){
    int i;
	srand(time(0));
	for(i = 0; i < tamanho; i++){
		v[i] = RandomInteger (1, 110000);	
	}
}

void Intercala (int p, int q, int r, int v[]) {
	 int i, j, k, *w;
     w = malloc ((r-p) * sizeof (int));
     i = p; j = q; k = 0;
     while (i < q && j < r) {
           if (v[i] <= v[j]) w[k++] = v[i++];
           else w[k++] = v[j++];
     }
     while (i < q) w[k++] = v[i++];
     while (j < r) w[k++] = v[j++];
     for (i = p; i < r; i++) v[i] = w[i-p];
     free (w);
}

void Mergesort (int p, int r, int v[]) {
     if (p < r - 1) {
        int q = (p + r)/2;
       // printf ("Mergesort(%2d, %2d, v)\n", p, q);
       // printf ("Mergesort(%2d, %2d, v)\n", q, r);
        Mergesort (p, q, v);
        Mergesort (q, r, v);
        Intercala (p, q, r, v);
     }
}

void main (int argc, char **argv){
	int world_rank;
	int world_size;

	/* Inicializando o MPI*/
	MPI_Init(&argc, &argv);
	MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);
	MPI_Comm_size(MPI_COMM_WORLD, &world_size);

	if (world_rank == 0){
		gera_vetor(v, TAM);
	}
		
	/* Dividindo o vetor em partes iguais de acordo com o numero total de processos */
	int size = TAM/world_size;
	
	/* Subvetores para cada processo ordenar*/
	int *sub_array = malloc(size * sizeof(int));
	MPI_Scatter(v, size, MPI_INT, sub_array, size, MPI_INT, 0, MPI_COMM_WORLD);
	
	/* Rodando o mergesort em cada processo pros subvetores */
	Mergesort(0, size, sub_array);

	/*Juntando os subvetores ordenados em um unico vetor*/
	int *sorted = NULL;

	if(world_rank == 0) {
		sorted = malloc(TAM * sizeof(int));	
	}
	
	MPI_Gather(sub_array, size, MPI_INT, sorted, size, MPI_INT, 0, MPI_COMM_WORLD);
	MPI_Barrier(MPI_COMM_WORLD);

	if(world_rank == 0) {
		/* Ordenado subvetores de cada processo entre eles */
		Mergesort(0, TAM, sorted);
			
		/* Limpando vetor */
		free(sorted);	
	}
	
	/* Limpando os subvetores */
	free(sub_array);
	
	/* Finalizando o MPI */
	MPI_Finalize();	
	
}

merge_sort_sequencial.c

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

#define MAX_LINHAS_DEBUG    20
#define TAM                 600000

int contador = 0;

int RandomInteger (int low, int high)
{
    int k;
    double d;
    d = (double) rand () / ((double) RAND_MAX + 1);
    k = d * (high - low + 1);
    return low + k;
}

void gera_vetor(int v[], int tamanho){
    int i;
    srand(time(0));
    for(i = 0; i < tamanho; i++){
        v[i] = RandomInteger (1, 110000);   
    }
}

void Intercala (int p, int q, int r, int v[]) {
int i, j, k, *w;
     w = malloc ((r-p) * sizeof (int));
     i = p; j = q; k = 0;
     while (i < q && j < r) {
           if (v[i] <= v[j]) w[k++] = v[i++];
           else w[k++] = v[j++];
     }
     while (i < q) w[k++] = v[i++];
     while (j < r) w[k++] = v[j++];
     for (i = p; i < r; i++) v[i] = w[i-p];
     free (w);
}
void Mergesort (int p, int r, int v[]) {
     if (p < r - 1) {
        int q = (p + r)/2;
        //printf ("Mergesort(%2d, %2d, v)\n", p, q);
        // printf ("Mergesort(%2d, %2d, v)\n", q, r);
        // system ("pause");
        Mergesort (p, q, v);
        Mergesort (q, r, v);
        Intercala (p, q, r, v);
     }
}

void main (){
    int v[TAM], tp_inicial, tp_final;
    gera_vetor(v, TAM);
    Mergesort(0, TAM, v);
}