ppr3

#include <iostream>
#include <algorithm>
#include<stdlib.h>
#include <time.h>
#include <mpi.h>
#include <cmath>

#define MASTER 0
using namespace std;
void bubblesort(int *v, int n);
int* merge(int* v1, int n1, int* v2, int n2);

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

	MPI_Init(&argc, &argv);
    int n=100;
	int *a = new int[n];
	int rank,size,length;
	int kawalki;
	int *data = NULL;
	int buforN;
	int *bufor = NULL;
	int *kawalki_wys = NULL;
	char hostname[MPI_MAX_PROCESSOR_NAME];
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);
	MPI_Comm_size(MPI_COMM_WORLD, &size);
	MPI_Get_processor_name(hostname, &length);



	if(rank == MASTER){
		srand(time(NULL));

		//if (n%size == 0){
	//		kawalki = n/size; //n=8 size=3 8/3=2
	//	}else{
	//		kawalki = ceil((double)n/size);
	//	}
		kawalki = n/size;
		if(n%size!=0){
			kawalki++;
		}
		cout<<"Kawalki: "<< kawalki <<endl;

		data = new int[size*kawalki];
		cout << "Tablica wyjsciowa " << endl;
		//	for (int i = 0; i<size*kawalki; i++) {
				//a[i] = rand() % 1000;
				//if(i < n){
				//	data[i] = rand() %1000;
			//	} else{
			//		data[i] = 0;
			//	}


		//	}
			for(int i=0; i<n; i++){
				data[i] = rand() %1000;
			    cout << data[i] << endl;
			}
			for(int i=n; i<size*kawalki; i++){
				data[i] = 0;
			   //cout << data[i] << endl;
			}


	}
	MPI_Barrier(MPI_COMM_WORLD);
	double timestart = MPI_Wtime();

	MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);

	//if (n%size == 0){
	//		kawalki = n/size; //n=8 size=3 8/3=2
	//	}else{
	//		kawalki = ceil((double)n/size);
	//	}
	kawalki = n/size;
		if(n%size!=0){
			kawalki++;
		}
	bufor = new int[kawalki];

	MPI_Scatter(data, kawalki, MPI_INT, bufor, kawalki, MPI_INT, 0, MPI_COMM_WORLD);
	/*
	cout<<"Bufor dla procesu: "<< rank <<endl;
	for(int i=0; i<kawalki; i++){
		cout<<bufor[i]<<endl;
	}
	*/
	delete[] data;
	data = NULL;

	 if(size-1!=rank){
		buforN = kawalki;
	 }else{
	 	buforN = n - kawalki*rank;
	 }

	 //if(n>=kawalki*(rank+1))

	bubblesort(bufor, buforN);
	/*
	cout<<"==============="<<endl;
	cout<<"Posortowany Bufor dla procesu: "<< rank <<endl;
	for(int i=0; i<buforN; i++){
		cout<<bufor[i]<<endl;
	}
	cout<<"==============="<<endl;
	*/
	int krok;
	int s_wys;
	for(krok=1; krok<size; krok=krok*2){ //tu wejdzie 1 3 5
		if((rank % (2*krok))!=0){
			MPI_Send(bufor, buforN, MPI_INT, rank-krok,0,MPI_COMM_WORLD);
			break;
		}
		if(rank + krok < size){
			if(n >= kawalki * ( rank+2*krok )){ //czy to dziala i dlczego czy id+krok
	 			s_wys = kawalki * krok;
			}else{
				s_wys = n-(kawalki*(rank+krok));
			}
			kawalki_wys = new int[s_wys];
			MPI_Status status;
			MPI_Recv(kawalki_wys, s_wys, MPI_INT, rank+krok, 0, MPI_COMM_WORLD, &status);
			data = merge(bufor, buforN, kawalki_wys, s_wys);
			delete[] bufor;
			delete[] kawalki_wys;
			bufor = data;
			buforN = buforN+s_wys;
			//bubblesort(bufor, buforN);

	}
}


	if(rank == MASTER){
		cout<<"\nTablica posortowana o wielkosci "<<buforN<<endl;
		for(int i=0; i<buforN; i++ ){
			cout<< bufor[i]<<endl;
		}
		cout<<"\nLiczba procesow: "<<size<<endl;
		cout<<"Czas: "<<MPI_Wtime()-timestart<<endl;
	}

	//cout << "Tablica a posortowana " << endl;
	//for (int i = 0; i<n; i++) cout << a[i] << endl;

	MPI_Finalize();
	return 0;
}

void bubblesort(int *v, int n){
	for (int i = n - 2; i >= 0; i--)
		for (int j = 0; j <= i; j++)
			if (v[j] > v[j + 1]){
				swap(v[j], v[j + 1]);
			}
}

int* merge(int* v1, int n1, int* v2, int n2){
	int *merged = new int[n1+n2];

	int i=0;
	int j=0;
	int k;

	for(k=0; k<n1+n2; k++){
		if(i>= n1){
			merged[k]=v2[j];
			j++;
		}
		else if(j >= n2){
			merged[k]=v2[i];
			i++;
		}
		else if(v1[i]<v2[j]){
			merged[k]=v1[i];
			i++;
		}
		else{ //v2[j] <= v1[i]
			merged[k] = v2[j];
			j++;
		}
	}

	return merged;
}