hpc_merge

#include <iostream>
#include <omp.h>

using namespace std;

void merge(int arr[], int low, int mid, int high) {
    // Create arrays of left and right partititons
    int n1 = mid - low + 1;
    int n2 = high - mid;

    int left[n1];
    int right[n2];

    // Copy all left elements
    for (int i = 0; i < n1; i++) left[i] = arr[low + i];
    // Copy all right elements
    for (int j = 0; j < n2; j++) right[j] = arr[mid + 1 + j];
    // Compare and place elements
    int i = 0, j = 0, k = low;
    while (i < n1 && j < n2) {
        if (left[i] <= right[j]){
            arr[k] = left[i];
            i++;
        }
        else{
            arr[k] = right[j];
            j++;
        }
        k++;
    }

    // If any elements are left out
    while (i < n1) {
        arr[k] = left[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = right[j];
        j++;
        k++;
    }
}

void parallelMergeSort(int arr[], int low, int high) {
    if (low < high) {
        int mid = (low + high) / 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 mergeSort(int arr[], int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2;
        mergeSort(arr, low, mid);
        mergeSort(arr, mid + 1, high);
        merge(arr, low, mid, high);
    }
}

int main() {
    int n;
    cout<<"Enter the maximum element: ";
    cin>>n;
    int arr[n];
    double start_time, end_time;

    // Create an array with numbers starting from n to 1.
    for(int i = 0, j = n; i < n; i++, j--) arr[i] = j;

    // Measure Sequential Time
    start_time = omp_get_wtime();
    mergeSort(arr, 0, n - 1);
    end_time = omp_get_wtime();
    cout << "Time taken by sequential algorithm: " << end_time - start_time << " seconds\n"<<endl;
    cout<<endl;

    // Print sorted array
    cout << "Sequential Sorted Array: ";
    for(int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    cout<<endl;

    // Reset the array
    for(int i = 0, j = n; i < n; i++, j--) arr[i] = j;

    //Measure Parallel time
    start_time = omp_get_wtime() ;
    parallelMergeSort(arr, 0, n - 1);
    end_time = omp_get_wtime();
    cout << "Time taken by parallel algorithm: " << end_time - start_time << " seconds"<<endl;
    cout<<endl;

    // Print sorted array
    cout << "Parallel Sorted Array: ";
    for(int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}

/*
This code demonstrates the parallel implementation of the merge sort algorithm using OpenMP. Let's break it down step by step:

**Merge Sort Overview:**
- Merge sort is a popular sorting algorithm that follows the divide and conquer approach.
- It divides the input array into two halves, recursively sorts the halves, and then merges them.
- The merge step involves comparing elements from the two halves and placing them in sorted order.
- Merge sort has a time complexity of O(n log n) for all cases (best, average, and worst).

**Code Explanation:**
1. **`merge()` Function:** This function merges two sorted subarrays into a single sorted array.
   - It takes four parameters: the array `arr[]`, indices `low`, `mid`, and `high` representing the two subarrays.
   - It creates temporary arrays `left[]` and `right[]` to store the elements of the left and right subarrays respectively.
   - It compares elements from `left[]` and `right[]`, placing the smaller element in the original array `arr[]`.
   - After merging, any remaining elements in `left[]` or `right[]` are copied to `arr[]`.

2. **`mergeSort()` Function:** This is the sequential implementation of merge sort.
   - It recursively divides the array into two halves until each subarray contains only one element.
   - It then merges the sorted halves using the `merge()` function.

3. **`parallelMergeSort()` Function:** This function is the parallel implementation of merge sort using OpenMP.
   - Similar to `mergeSort()`, it recursively divides the array into two halves.
   - However, the division of work is parallelized using OpenMP sections.
   - Each section recursively sorts its assigned portion of the array, and then the sorted halves are merged.

4. **`main()` Function:**
   - It initializes the input array with numbers from `n` to 1.
   - It measures the time taken for sequential merge sort and prints the sorted array.
   - Then, it resets the array, measures the time taken for parallel merge sort, and prints the sorted array.

**Time Complexity Analysis:**
- Merge sort has a time complexity of O(n log n) for all cases (best, average, and worst).
- In the parallel implementation, the work is divided among multiple threads using OpenMP sections.
- However, the merging step remains inherently sequential, as merging two sorted arrays cannot be parallelized efficiently.
- Despite the parallelization, the overall time complexity of the parallel merge sort algorithm remains O(n log n).

In summary, this code demonstrates how merge sort can be parallelized using OpenMP to potentially
improve performance while maintaining the same time complexity as the sequential version.
*/