#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>
#define N 1000000 // Number of random numbers in total
int compare(const void *a, const void *b) {
return (*(double*)a > *(double*)b) - (*(double*)a < *(double*)b);
}
int main(int argc, char *argv[]) {
int rank, size;
double *global_data = NULL;
double *local_data;
int local_n;
double start_time, end_time;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &size);
local_n = N / size; // Number of elements per process
if (N % size > rank) {
local_n++;
}
local_data
= (double *)malloc(local_n
* sizeof(double));
// Root process generates the full data set
if (rank == 0) {
global_data
= (double *)malloc(N
* sizeof(double)); srand(0); // Use a fixed seed for reproducibility for (int i = 0; i < N; i++) {
global_data
[i
] = (double)rand() / RAND_MAX
; }
}
// Distribute portions of the array to all processes
if (rank == 0) {
// Calculate displacements and counts for distribution
int *displs
= malloc(size
* sizeof(int)); int *sendcounts
= malloc(size
* sizeof(int)); int disp = 0;
for (int i = 0; i < size; i++) {
sendcounts[i] = N / size;
if (i < N % size) sendcounts[i]++;
displs[i] = disp;
disp += sendcounts[i];
}
MPI_Scatterv(global_data, sendcounts, displs, MPI_DOUBLE, local_data, local_n, MPI_DOUBLE, 0, MPI_COMM_WORLD);
} else {
MPI_Scatterv(NULL, NULL, NULL, MPI_DOUBLE, local_data, local_n, MPI_DOUBLE, 0, MPI_COMM_WORLD);
}
// Sort local data
qsort(local_data
, local_n
, sizeof(double), compare
);
// Gather sorted data back at root
if (rank == 0) {
int *recvcounts
= malloc(size
* sizeof(int)); int *displs
= malloc(size
* sizeof(int)); int disp = 0;
for (int i = 0; i < size; i++) {
recvcounts[i] = N / size;
if (i < N % size) recvcounts[i]++;
displs[i] = disp;
disp += recvcounts[i];
}
MPI_Gatherv(local_data, local_n, MPI_DOUBLE, global_data, recvcounts, displs, MPI_DOUBLE, 0, MPI_COMM_WORLD);
// Sort the entire array at root
qsort(global_data
, N
, sizeof(double), compare
);
} else {
MPI_Gatherv(local_data, local_n, MPI_DOUBLE, NULL, NULL, NULL, MPI_DOUBLE, 0, MPI_COMM_WORLD);
}
// Print results if needed
if (rank == 0) {
for (int i = 0; i < N; i++) {
printf("%f ", global_data
[i
]); }
}
MPI_Finalize();
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPG1waS5oPgoKI2RlZmluZSBOIDEwMDAwMDAgLy8gTnVtYmVyIG9mIHJhbmRvbSBudW1iZXJzIGluIHRvdGFsCgppbnQgY29tcGFyZShjb25zdCB2b2lkICphLCBjb25zdCB2b2lkICpiKSB7CiAgICByZXR1cm4gKCooZG91YmxlKilhID4gKihkb3VibGUqKWIpIC0gKCooZG91YmxlKilhIDwgKihkb3VibGUqKWIpOwp9CgppbnQgbWFpbihpbnQgYXJnYywgY2hhciAqYXJndltdKSB7CiAgICBpbnQgcmFuaywgc2l6ZTsKICAgIGRvdWJsZSAqZ2xvYmFsX2RhdGEgPSBOVUxMOwogICAgZG91YmxlICpsb2NhbF9kYXRhOwogICAgaW50IGxvY2FsX247CiAgICBkb3VibGUgc3RhcnRfdGltZSwgZW5kX3RpbWU7CgogICAgTVBJX0luaXQoJmFyZ2MsICZhcmd2KTsKICAgIE1QSV9Db21tX3JhbmsoTVBJX0NPTU1fV09STEQsICZyYW5rKTsKICAgIE1QSV9Db21tX3NpemUoTVBJX0NPTU1fV09STEQsICZzaXplKTsKCiAgICBsb2NhbF9uID0gTiAvIHNpemU7ICAvLyBOdW1iZXIgb2YgZWxlbWVudHMgcGVyIHByb2Nlc3MKICAgIGlmIChOICUgc2l6ZSA+IHJhbmspIHsKICAgICAgICBsb2NhbF9uKys7CiAgICB9CgogICAgbG9jYWxfZGF0YSA9IChkb3VibGUgKiltYWxsb2MobG9jYWxfbiAqIHNpemVvZihkb3VibGUpKTsKCiAgICAvLyBSb290IHByb2Nlc3MgZ2VuZXJhdGVzIHRoZSBmdWxsIGRhdGEgc2V0CiAgICBpZiAocmFuayA9PSAwKSB7CiAgICAgICAgZ2xvYmFsX2RhdGEgPSAoZG91YmxlICopbWFsbG9jKE4gKiBzaXplb2YoZG91YmxlKSk7CiAgICAgICAgc3JhbmQoMCk7IC8vIFVzZSBhIGZpeGVkIHNlZWQgZm9yIHJlcHJvZHVjaWJpbGl0eQogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgTjsgaSsrKSB7CiAgICAgICAgICAgIGdsb2JhbF9kYXRhW2ldID0gKGRvdWJsZSlyYW5kKCkgLyBSQU5EX01BWDsKICAgICAgICB9CiAgICB9CgogICAgLy8gRGlzdHJpYnV0ZSBwb3J0aW9ucyBvZiB0aGUgYXJyYXkgdG8gYWxsIHByb2Nlc3NlcwogICAgaWYgKHJhbmsgPT0gMCkgewogICAgICAgIC8vIENhbGN1bGF0ZSBkaXNwbGFjZW1lbnRzIGFuZCBjb3VudHMgZm9yIGRpc3RyaWJ1dGlvbgogICAgICAgIGludCAqZGlzcGxzID0gbWFsbG9jKHNpemUgKiBzaXplb2YoaW50KSk7CiAgICAgICAgaW50ICpzZW5kY291bnRzID0gbWFsbG9jKHNpemUgKiBzaXplb2YoaW50KSk7CiAgICAgICAgaW50IGRpc3AgPSAwOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgc2l6ZTsgaSsrKSB7CiAgICAgICAgICAgIHNlbmRjb3VudHNbaV0gPSBOIC8gc2l6ZTsKICAgICAgICAgICAgaWYgKGkgPCBOICUgc2l6ZSkgc2VuZGNvdW50c1tpXSsrOwogICAgICAgICAgICBkaXNwbHNbaV0gPSBkaXNwOwogICAgICAgICAgICBkaXNwICs9IHNlbmRjb3VudHNbaV07CiAgICAgICAgfQoKICAgICAgICBNUElfU2NhdHRlcnYoZ2xvYmFsX2RhdGEsIHNlbmRjb3VudHMsIGRpc3BscywgTVBJX0RPVUJMRSwgbG9jYWxfZGF0YSwgbG9jYWxfbiwgTVBJX0RPVUJMRSwgMCwgTVBJX0NPTU1fV09STEQpOwoKICAgICAgICBmcmVlKGRpc3Bscyk7CiAgICAgICAgZnJlZShzZW5kY291bnRzKTsKICAgIH0gZWxzZSB7CiAgICAgICAgTVBJX1NjYXR0ZXJ2KE5VTEwsIE5VTEwsIE5VTEwsIE1QSV9ET1VCTEUsIGxvY2FsX2RhdGEsIGxvY2FsX24sIE1QSV9ET1VCTEUsIDAsIE1QSV9DT01NX1dPUkxEKTsKICAgIH0KCiAgICAvLyBTb3J0IGxvY2FsIGRhdGEKICAgIHFzb3J0KGxvY2FsX2RhdGEsIGxvY2FsX24sIHNpemVvZihkb3VibGUpLCBjb21wYXJlKTsKCiAgICAvLyBHYXRoZXIgc29ydGVkIGRhdGEgYmFjayBhdCByb290CiAgICBpZiAocmFuayA9PSAwKSB7CiAgICAgICAgaW50ICpyZWN2Y291bnRzID0gbWFsbG9jKHNpemUgKiBzaXplb2YoaW50KSk7CiAgICAgICAgaW50ICpkaXNwbHMgPSBtYWxsb2Moc2l6ZSAqIHNpemVvZihpbnQpKTsKICAgICAgICBpbnQgZGlzcCA9IDA7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBzaXplOyBpKyspIHsKICAgICAgICAgICAgcmVjdmNvdW50c1tpXSA9IE4gLyBzaXplOwogICAgICAgICAgICBpZiAoaSA8IE4gJSBzaXplKSByZWN2Y291bnRzW2ldKys7CiAgICAgICAgICAgIGRpc3Bsc1tpXSA9IGRpc3A7CiAgICAgICAgICAgIGRpc3AgKz0gcmVjdmNvdW50c1tpXTsKICAgICAgICB9CgogICAgICAgIE1QSV9HYXRoZXJ2KGxvY2FsX2RhdGEsIGxvY2FsX24sIE1QSV9ET1VCTEUsIGdsb2JhbF9kYXRhLCByZWN2Y291bnRzLCBkaXNwbHMsIE1QSV9ET1VCTEUsIDAsIE1QSV9DT01NX1dPUkxEKTsKCiAgICAgICAgLy8gU29ydCB0aGUgZW50aXJlIGFycmF5IGF0IHJvb3QKICAgICAgICBxc29ydChnbG9iYWxfZGF0YSwgTiwgc2l6ZW9mKGRvdWJsZSksIGNvbXBhcmUpOwoKICAgICAgICBmcmVlKHJlY3Zjb3VudHMpOwogICAgICAgIGZyZWUoZGlzcGxzKTsKICAgIH0gZWxzZSB7CiAgICAgICAgTVBJX0dhdGhlcnYobG9jYWxfZGF0YSwgbG9jYWxfbiwgTVBJX0RPVUJMRSwgTlVMTCwgTlVMTCwgTlVMTCwgTVBJX0RPVUJMRSwgMCwgTVBJX0NPTU1fV09STEQpOwogICAgfQoKICAgIC8vIFByaW50IHJlc3VsdHMgaWYgbmVlZGVkCiAgICBpZiAocmFuayA9PSAwKSB7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBOOyBpKyspIHsKICAgICAgICAgICAgcHJpbnRmKCIlZiAiLCBnbG9iYWxfZGF0YVtpXSk7CiAgICAgICAgfQogICAgICAgIHByaW50ZigiXG4iKTsKICAgICAgICBmcmVlKGdsb2JhbF9kYXRhKTsKICAgIH0KCiAgICBmcmVlKGxvY2FsX2RhdGEpOwogICAgTVBJX0ZpbmFsaXplKCk7CiAgICByZXR1cm4gMDsKfQo=