#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);

        free(displs);
        free(sendcounts);
    } 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);

        free(recvcounts);
        free(displs);
    } 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]);
        }
        printf("\n");
        free(global_data);
    }

    free(local_data);
    MPI_Finalize();
    return 0;
}

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPG1waS5oPgoKI2RlZmluZSBOIDEwMDAwMDAgLy8gTnVtYmVyIG9mIHJhbmRvbSBudW1iZXJzIGluIHRvdGFsCgppbnQgY29tcGFyZShjb25zdCB2b2lkICphLCBjb25zdCB2b2lkICpiKSB7CiAgICByZXR1cm4gKCooZG91YmxlKilhID4gKihkb3VibGUqKWIpIC0gKCooZG91YmxlKilhIDwgKihkb3VibGUqKWIpOwp9CgppbnQgbWFpbihpbnQgYXJnYywgY2hhciAqYXJndltdKSB7CiAgICBpbnQgcmFuaywgc2l6ZTsKICAgIGRvdWJsZSAqZ2xvYmFsX2RhdGEgPSBOVUxMOwogICAgZG91YmxlICpsb2NhbF9kYXRhOwogICAgaW50IGxvY2FsX247CiAgICBkb3VibGUgc3RhcnRfdGltZSwgZW5kX3RpbWU7CgogICAgTVBJX0luaXQoJmFyZ2MsICZhcmd2KTsKICAgIE1QSV9Db21tX3JhbmsoTVBJX0NPTU1fV09STEQsICZyYW5rKTsKICAgIE1QSV9Db21tX3NpemUoTVBJX0NPTU1fV09STEQsICZzaXplKTsKCiAgICBsb2NhbF9uID0gTiAvIHNpemU7ICAvLyBOdW1iZXIgb2YgZWxlbWVudHMgcGVyIHByb2Nlc3MKICAgIGlmIChOICUgc2l6ZSA+IHJhbmspIHsKICAgICAgICBsb2NhbF9uKys7CiAgICB9CgogICAgbG9jYWxfZGF0YSA9IChkb3VibGUgKiltYWxsb2MobG9jYWxfbiAqIHNpemVvZihkb3VibGUpKTsKCiAgICAvLyBSb290IHByb2Nlc3MgZ2VuZXJhdGVzIHRoZSBmdWxsIGRhdGEgc2V0CiAgICBpZiAocmFuayA9PSAwKSB7CiAgICAgICAgZ2xvYmFsX2RhdGEgPSAoZG91YmxlICopbWFsbG9jKE4gKiBzaXplb2YoZG91YmxlKSk7CiAgICAgICAgc3JhbmQoMCk7IC8vIFVzZSBhIGZpeGVkIHNlZWQgZm9yIHJlcHJvZHVjaWJpbGl0eQogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgTjsgaSsrKSB7CiAgICAgICAgICAgIGdsb2JhbF9kYXRhW2ldID0gKGRvdWJsZSlyYW5kKCkgLyBSQU5EX01BWDsKICAgICAgICB9CiAgICB9CgogICAgLy8gRGlzdHJpYnV0ZSBwb3J0aW9ucyBvZiB0aGUgYXJyYXkgdG8gYWxsIHByb2Nlc3NlcwogICAgaWYgKHJhbmsgPT0gMCkgewogICAgICAgIC8vIENhbGN1bGF0ZSBkaXNwbGFjZW1lbnRzIGFuZCBjb3VudHMgZm9yIGRpc3RyaWJ1dGlvbgogICAgICAgIGludCAqZGlzcGxzID0gbWFsbG9jKHNpemUgKiBzaXplb2YoaW50KSk7CiAgICAgICAgaW50ICpzZW5kY291bnRzID0gbWFsbG9jKHNpemUgKiBzaXplb2YoaW50KSk7CiAgICAgICAgaW50IGRpc3AgPSAwOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgc2l6ZTsgaSsrKSB7CiAgICAgICAgICAgIHNlbmRjb3VudHNbaV0gPSBOIC8gc2l6ZTsKICAgICAgICAgICAgaWYgKGkgPCBOICUgc2l6ZSkgc2VuZGNvdW50c1tpXSsrOwogICAgICAgICAgICBkaXNwbHNbaV0gPSBkaXNwOwogICAgICAgICAgICBkaXNwICs9IHNlbmRjb3VudHNbaV07CiAgICAgICAgfQoKICAgICAgICBNUElfU2NhdHRlcnYoZ2xvYmFsX2RhdGEsIHNlbmRjb3VudHMsIGRpc3BscywgTVBJX0RPVUJMRSwgbG9jYWxfZGF0YSwgbG9jYWxfbiwgTVBJX0RPVUJMRSwgMCwgTVBJX0NPTU1fV09STEQpOwoKICAgICAgICBmcmVlKGRpc3Bscyk7CiAgICAgICAgZnJlZShzZW5kY291bnRzKTsKICAgIH0gZWxzZSB7CiAgICAgICAgTVBJX1NjYXR0ZXJ2KE5VTEwsIE5VTEwsIE5VTEwsIE1QSV9ET1VCTEUsIGxvY2FsX2RhdGEsIGxvY2FsX24sIE1QSV9ET1VCTEUsIDAsIE1QSV9DT01NX1dPUkxEKTsKICAgIH0KCiAgICAvLyBTb3J0IGxvY2FsIGRhdGEKICAgIHFzb3J0KGxvY2FsX2RhdGEsIGxvY2FsX24sIHNpemVvZihkb3VibGUpLCBjb21wYXJlKTsKCiAgICAvLyBHYXRoZXIgc29ydGVkIGRhdGEgYmFjayBhdCByb290CiAgICBpZiAocmFuayA9PSAwKSB7CiAgICAgICAgaW50ICpyZWN2Y291bnRzID0gbWFsbG9jKHNpemUgKiBzaXplb2YoaW50KSk7CiAgICAgICAgaW50ICpkaXNwbHMgPSBtYWxsb2Moc2l6ZSAqIHNpemVvZihpbnQpKTsKICAgICAgICBpbnQgZGlzcCA9IDA7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBzaXplOyBpKyspIHsKICAgICAgICAgICAgcmVjdmNvdW50c1tpXSA9IE4gLyBzaXplOwogICAgICAgICAgICBpZiAoaSA8IE4gJSBzaXplKSByZWN2Y291bnRzW2ldKys7CiAgICAgICAgICAgIGRpc3Bsc1tpXSA9IGRpc3A7CiAgICAgICAgICAgIGRpc3AgKz0gcmVjdmNvdW50c1tpXTsKICAgICAgICB9CgogICAgICAgIE1QSV9HYXRoZXJ2KGxvY2FsX2RhdGEsIGxvY2FsX24sIE1QSV9ET1VCTEUsIGdsb2JhbF9kYXRhLCByZWN2Y291bnRzLCBkaXNwbHMsIE1QSV9ET1VCTEUsIDAsIE1QSV9DT01NX1dPUkxEKTsKCiAgICAgICAgLy8gU29ydCB0aGUgZW50aXJlIGFycmF5IGF0IHJvb3QKICAgICAgICBxc29ydChnbG9iYWxfZGF0YSwgTiwgc2l6ZW9mKGRvdWJsZSksIGNvbXBhcmUpOwoKICAgICAgICBmcmVlKHJlY3Zjb3VudHMpOwogICAgICAgIGZyZWUoZGlzcGxzKTsKICAgIH0gZWxzZSB7CiAgICAgICAgTVBJX0dhdGhlcnYobG9jYWxfZGF0YSwgbG9jYWxfbiwgTVBJX0RPVUJMRSwgTlVMTCwgTlVMTCwgTlVMTCwgTVBJX0RPVUJMRSwgMCwgTVBJX0NPTU1fV09STEQpOwogICAgfQoKICAgIC8vIFByaW50IHJlc3VsdHMgaWYgbmVlZGVkCiAgICBpZiAocmFuayA9PSAwKSB7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBOOyBpKyspIHsKICAgICAgICAgICAgcHJpbnRmKCIlZiAiLCBnbG9iYWxfZGF0YVtpXSk7CiAgICAgICAgfQogICAgICAgIHByaW50ZigiXG4iKTsKICAgICAgICBmcmVlKGdsb2JhbF9kYXRhKTsKICAgIH0KCiAgICBmcmVlKGxvY2FsX2RhdGEpOwogICAgTVBJX0ZpbmFsaXplKCk7CiAgICByZXR1cm4gMDsKfQo=