#include <iostream>
#include <vector>
#include <thread>
#include <mutex>
#include <algorithm>

using namespace std;

mutex mtx; // Mutex to synchronize access to shared histogram

// Function to generate a histogram for a portion of the array
void generateHistogram(const vector<int>& arr, int start, int end, vector<int>& histogram, int minVal) {
    for (int i = start; i < end; ++i) {
        int index = arr[i] - minVal; // Find the position in histogram
        mtx.lock();
        histogram[index]++; // Update histogram safely
        mtx.unlock();
    }

    // Display the thread's work
    cout << "Thread " << this_thread::get_id() << " processed indices [" << start << ", " << end - 1 << "]\n";
}

// Function to perform distributed histogram sort
void distributedHistogramSort(vector<int>& arr, int numThreads) {
    // Find the range of elements in the array (min and max)
    int minElem = *min_element(arr.begin(), arr.end());
    int maxElem = *max_element(arr.begin(), arr.end());

    int range = maxElem - minElem + 1; // Range of values in the array
    vector<int> histogram(range, 0);   // Histogram to count occurrences of each element

    // Determine the chunk size for each thread
    int chunkSize = arr.size() / numThreads;
    vector<thread> threads;

    // Create threads to generate histograms in parallel
    for (int i = 0; i < numThreads; ++i) {
        int start = i * chunkSize;
        int end = (i == numThreads - 1) ? arr.size() : (i + 1) * chunkSize;
        
        // Each thread generates a histogram for a portion of the array
        threads.push_back(thread(generateHistogram, ref(arr), start, end, ref(histogram), minElem));
    }

    // Wait for all threads to finish
    for (auto& t : threads) {
        t.join();
    }

    // Reconstruct the sorted array based on the histogram
    vector<int> sortedArr;
    for (int i = 0; i < range; ++i) {
        sortedArr.insert(sortedArr.end(), histogram[i], i + minElem);
    }

    // Copy the sorted data back into the original array
    arr = sortedArr;
}

int main() {
    // Example unsorted array
    vector<int> arr = {12, 3, 5, 7, 19, 2, 8, 13, 4, 15, 6, 11, 10};

    int numThreads = 4; // Number of threads to use for parallelism

    cout << "Unsorted Array:\n";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    // Perform distributed histogram sort
    distributedHistogramSort(arr, numThreads);

    cout << "Sorted Array:\n";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}