/*
 * 04-parallel-sort.c  —  LAB 2: Parallel Sort using MPI
 * Session 11 · 2311CSC501J Parallel Processing
 *
 * THE IDEA  (a distributed sort in four moves)
 *   Sorting a huge array on one machine is slow. Split the work across processes:
 *
 *     1. SCATTER : rank 0 splits the array into equal chunks, one per process.
 *     2. LOCAL   : each process sorts ITS OWN chunk (here with the C library
 *                  qsort) — this happens on all processes at the same time.
 *     3. GATHER  : the sorted chunks come back to rank 0, concatenated. Now rank 0
 *                  holds `size` sorted RUNS sitting next to each other — but the
 *                  array as a WHOLE is not sorted yet.
 *     4. MERGE   : rank 0 does a k-way merge of those already-sorted runs into one
 *                  fully sorted array. Merging pre-sorted runs is cheap and linear.
 *
 *   This is the classic pattern behind real distributed sorts (e.g. sample sort /
 *   the sort phase of MapReduce): do the expensive sorting in parallel, then pay a
 *   small, simple merge at the end.
 *
 *   Note: this simple version uses the basic MPI_Scatter/MPI_Gather, which require
 *   equal-sized chunks, so the total size must divide evenly among the processes.
 *   We enforce that by making total = PER * size. (Uneven splits use the more
 *   advanced MPI_Scatterv / MPI_Gatherv.)
 *
 * HOW TO COMPILE & RUN
 *       mpicc 04-parallel-sort.c -o psort
 *       mpirun -np 4 ./psort        # 4 processes, 6 elements each -> 24 total
 *       mpirun -np 2 ./psort        # works for any process count
 *   Cannot run in a browser. See README.md for no-install online options.
 */

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

#define PER 6          /* elements per process; total array size = PER * size */

/* Comparator for qsort: sort ints ascending. Returns <0, 0, or >0. */
static int cmp_int(const void *a, const void *b) {
    int x = *(const int *)a;
    int y = *(const int *)b;
    return (x > y) - (x < y);      /* branchless, and never overflows */
}

/* k-way merge: `runs` holds `k` already-sorted blocks laid end to end, each of
 * length `run_len`. Merge them into `out` (length k*run_len), fully sorted. */
static void k_way_merge(const int *runs, int k, int run_len, int *out) {
    int *idx = (int *) calloc(k, sizeof(int));   /* how far we've consumed each run */
    int total = k * run_len;

    for (int n = 0; n < total; n++) {
        int best = -1;          /* which run currently offers the smallest value */
        int best_val = 0;
        for (int r = 0; r < k; r++) {
            if (idx[r] < run_len) {                       /* run r not exhausted  */
                int val = runs[r * run_len + idx[r]];     /* its current front    */
                if (best == -1 || val < best_val) {
                    best = r;
                    best_val = val;
                }
            }
        }
        out[n] = best_val;      /* take the smallest front element ...            */
        idx[best]++;            /* ... and advance that run                        */
    }
    free(idx);
}

int main(int argc, char **argv) {
    MPI_Init(&argc, &argv);

    int rank, size;
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &size);

    int per   = PER;
    int total = per * size;

    /* Rank 0 creates the unsorted array everyone will help sort. */
    int *data = NULL;
    if (rank == 0) {
        srand(42);              /* fixed seed => reproducible output for class */
        data = (int *) malloc(total * sizeof(int));
        printf("Unsorted (%d elements): ", total);
        for (int i = 0; i < total; i++) {
            data[i] = rand() % 100;        /* values 0..99 */
            printf("%d ", data[i]);
        }
        printf("\n");
    }

    /* 1. SCATTER: give each process its own chunk of `per` elements. */
    int *chunk = (int *) malloc(per * sizeof(int));
    MPI_Scatter(data, per, MPI_INT,
                chunk, per, MPI_INT,
                0, MPI_COMM_WORLD);

    /* 2. LOCAL SORT: every process sorts its chunk, all at the same time. */
    qsort(chunk, per, sizeof(int), cmp_int);

    /* 3. GATHER: sorted chunks return to rank 0, concatenated in rank order.
     *    `gathered` now holds `size` sorted runs, each `per` long. */
    int *gathered = NULL;
    if (rank == 0) gathered = (int *) malloc(total * sizeof(int));
    MPI_Gather(chunk, per, MPI_INT,
               gathered, per, MPI_INT,
               0, MPI_COMM_WORLD);

    /* 4. MERGE: rank 0 merges the sorted runs into one fully sorted array. */
    if (rank == 0) {
        int *sorted = (int *) malloc(total * sizeof(int));
        k_way_merge(gathered, size, per, sorted);

        printf("Sorted   (%d elements): ", total);
        for (int i = 0; i < total; i++) printf("%d ", sorted[i]);
        printf("\n");

        /* Verify: confirm the result is non-decreasing. */
        int ok = 1;
        for (int i = 1; i < total; i++)
            if (sorted[i - 1] > sorted[i]) { ok = 0; break; }
        printf("%s\n", ok ? "CORRECT — array is fully sorted." : "WRONG — not sorted!");

        free(sorted);
        free(gathered);
        free(data);
    }

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