Rewrite this code to add parallel quick sort and parallel counting sort: #include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <sys/time.h>
#include <omp.h>

using namespace std;

// Function prototypes for the sorting algorithms
void merge(vector<int> &arr, int low, int mid, int high);
void parallelMergeSort(vector<int> &arr, int low, int high);

// Function to measure execution time
double measureTime(void (*sortFunc)(vector<int> &, int, int), vector<int> &data, int numThreads);

int main() {
    int choice;
    const int MAX_VALUE = 1000; // Range: 0 to 1000

    cout << "Enter number of integers to sort (e.g., 1000000000 for 10^9): ";
    int N;
    cin >> N;

    cout << "Choose sorting algorithm:" << endl;
    cout << "1 - Parallel Merge Sort" << endl;
    cout << "(Note: Only Merge Sort is implemented in this example.)" << 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;
    if (choice == 1) {
        cout << "Running Parallel Merge Sort:" << endl;
        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(parallelMergeSort, temp, numThreads);
            }
            avgTime = totalTime / 5;
            cout << "Threads: " << numThreads << ", Avg Time: " << avgTime << " seconds." << endl;
        }
    } else {
        cerr << "Invalid choice." << endl;
        return 1;
    }

    return 0;
}

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

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