MPI sort example.

MPIsort.cpp

#include <mpi.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>

void bubble_sort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
}

void selection_sort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        int max_idx = i;
        for (int j = i + 1; j < n; ++j) {
            if (arr[j] > arr[max_idx]) {
                max_idx = j;
            }
        }
        std::swap(arr[i], arr[max_idx]);
    }
}

std::vector<int> merge(const std::vector<int>& arr1, const std::vector<int>& arr2) {
    std::vector<int> result(arr1.size() + arr2.size());
    std::merge(arr1.begin(), arr1.end(), arr2.begin(), arr2.end(), result.begin());
    return result;
}

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

    const int array_size = 80; // Assuming size * 10 is the total number of elements
    std::vector<int> data(array_size);
    std::vector<int> local_data(array_size / size);

    if (rank == 0) {
        srand(time(0));
        for (int i = 0; i < array_size; ++i) {
            data[i] = rand() % 100;
        }
        std::cout << "Original data: ";
        for (int i = 0; i < array_size; ++i) {
            std::cout << data[i] << " ";
        }
        std::cout << std::endl;
    }

    MPI_Scatter(data.data(), array_size / size, MPI_INT, local_data.data(), array_size / size, MPI_INT, 0, MPI_COMM_WORLD);

    if (rank % 2 == 0) {
        bubble_sort(local_data);
    } else {
        selection_sort(local_data);
    }

    std::cout << "Process " << rank << " sorted data: ";
    for (int i = 0; i < local_data.size(); ++i) {
        std::cout << local_data[i] << " ";
    }
    std::cout << std::endl;

    MPI_Gather(local_data.data(), array_size / size, MPI_INT, data.data(), array_size / size, MPI_INT, 0, MPI_COMM_WORLD);

    if (rank == 0) {
        std::vector<std::vector<int>> parts(size);

        for (int i = 0; i < size; ++i) {
            parts[i].assign(data.begin() + i * (array_size / size), data.begin() + (i + 1) * (array_size / size));
            if (i % 2 != 0) {
                std::reverse(parts[i].begin(), parts[i].end());
            }
        }

        while (parts.size() > 1) {
            std::vector<std::vector<int>> new_parts;
            for (size_t i = 0; i < parts.size(); i += 2) {
                if (i + 1 < parts.size()) {
                    new_parts.push_back(merge(parts[i], parts[i + 1]));
                } else {
                    new_parts.push_back(parts[i]);
                }
            }
            parts = new_parts;
        }

        auto final_sorted_data = parts[0];

        std::cout << "Final sorted data: ";
        for (int i = 0; i < final_sorted_data.size(); ++i) {
            std::cout << final_sorted_data[i] << " ";
        }
        std::cout << std::endl;
    }

    MPI_Finalize();
    return 0;
}