#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <sys/time.h>
#include <omp.h>

using namespace std;

void merge(vector<int> &arr, int low, int mid, int high) {
    int n1 = mid - low + 1;
    int n2 = high - mid;
    vector<int> L(n1), R(n2);

    for (int i = 0; i < n1; i++)
        L[i] = arr[low + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = low;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void parallelMergeSort(vector<int> &arr, int low, int high) {
    int mid;
    if (low < high) {
        mid = low + (high - low) / 2;
        #pragma omp parallel sections
        {
            #pragma omp section
            parallelMergeSort(arr, low, mid);
            #pragma omp section
            parallelMergeSort(arr, mid + 1, high);
        }
        merge(arr, low, mid, high);
    }
}

void parallelQuickSort(vector<int> &arr, int left, int right) {
    if (left < right) {
        int pivot = arr[left + (right - left) / 2];
        int i = left, j = right;
        while (i <= j) {
            while(arr[i] < pivot)
                i++;
            while(arr[j] > pivot)
                j--;
            if(i <= j) {
                swap(arr[i], arr[j]);
                i++;
                j--;
            }
        }
        #pragma omp parallel sections
        {
            #pragma omp section
            {
                parallelQuickSort(arr, left, j);
            }
            #pragma omp section
            {
                parallelQuickSort(arr, i, right);
            }
        }
    }
}

void parallelCountingSort(vector<int> &arr, int maxValue) {
    vector<int> count(maxValue + 1, 0);
    vector<int> output(arr.size());

    #pragma omp parallel for
    for (auto num : arr) {
        #pragma omp atomic
        count[num]++;
    }

    for (int i = 1; i <= maxValue; ++i) {
        count[i] += count[i - 1];
    }

    for (int i = (int)arr.size() - 1; i >= 0; --i) {
        output[count[arr[i]] - 1] = arr[i];
        #pragma omp atomic
        count[arr[i]]--;
    }

    arr = move(output);
}

void runParallelSort(void (*sortFunc)(vector<int> &, int, int), vector<int> &data, const vector<int> &thread_counts) {
    double totalTime, avgTime;
    vector<int> temp;
    for (int numThreads : thread_counts) {
        totalTime = 0.0;
        for (int i = 0; i < 5; ++i) { // 5 runs
            temp = data; // Copy the original data
            totalTime += measureTime(sortFunc, temp, numThreads);
        }
        avgTime = totalTime / 5;
        cout << "Threads: " << numThreads << ", Avg Time: " << avgTime << " seconds." << endl;
    }
}

void runParallelCountingSort(vector<int> &data, const vector<int> &thread_counts, int maxValue) {
    double totalTime, avgTime;
    vector<int> temp;
    for (int numThreads : thread_counts) {
        totalTime = 0.0;
        for (int i = 0; i < 5; ++i) {
            temp = data;
            totalTime += measureTime([maxValue](vector<int> &a, int, int) { parallelCountingSort(a, maxValue); }, temp, numThreads);
        }
        avgTime = totalTime / 5;
        cout << "Threads: " << numThreads << ", Avg Time: " << avgTime << " seconds." << endl;
    }
}

double measureTime(std::function<void(vector<int> &, int, int)> sortFunc, vector<int> &data, int numThreads) {
    omp_set_num_threads(numThreads);
    struct timeval start, end;
    gettimeofday(&start, NULL);
    sortFunc(data, 0, data.size() - 1);
    gettimeofday(&end, NULL);
    double elapsed = (end.tv_sec - start.tv_sec) + ((end.tv_usec - start.tv_usec) / 1000000.0);
    return elapsed;
}

double measureTime(void (*sortFunc)(vector<int> &, int, int), vector<int> &data, int numThreads) {
    omp_set_num_threads(numThreads);
    struct timeval start, end;
    gettimeofday(&start, NULL);
    sortFunc(data, 0, data.size() - 1);
    gettimeofday(&end, NULL);
    double elapsed = (end.tv_sec - start.tv_sec) + ((end.tv_usec - start.tv_usec) / 1000000.0);
    return elapsed;
}
int main() {
    int choice;
    const int MAX_VALUE = 1000; // Range: 0 to 1000

    int N=1_000_000_000;
    

    cout << "Choose sorting algorithm:" << endl;
    cout << "1 - Parallel Merge Sort" << endl;
    cout << "2 - Parallel Quick Sort" << endl;
    cout << "3 - Parallel Counting Sort" << endl;
    cout << "Selection: ";
    cin >> choice;

    vector<int> data(N), temp;
    srand(static_cast<unsigned>(time(0)));
    generate(data.begin(), data.end(), [&] { return rand() % (MAX_VALUE + 1); });

    vector<int> thread_counts = {1, 2, 4, 6, 8, 10, 12, 14, 16};
    double totalTime, avgTime;

    switch (choice) {
        case 1:
            cout << "Running Parallel Merge Sort:" << endl;
            runParallelSort(parallelMergeSort, data, thread_counts);
            break;
        case 2:
            cout << "Running Parallel Quick Sort:" << endl;
            runParallelSort(parallelQuickSort, data, thread_counts);
            break;
        case 3:
            cout << "Running Parallel Counting Sort (for MAX_VALUE = " << MAX_VALUE << "):" << endl;
            runParallelCountingSort(data, thread_counts, MAX_VALUE);
            break;
        default:
            cerr << "Invalid choice." << endl;
            return 1;
    }

    return 0;
}

correct this code