#include <iostream>
#include <vector>
using namespace std;

// Function to merge two sorted halves of the array into a single sorted array.
void merge(int arr[], int left, int mid, int right) {
    int n= left+ (right-left)/2;
    vector<int> tempArray;
    int start = left;
    int start2= mid+1;
    if(arr[mid]<=arr[start2]){
        return;
    }
    while(start<=mid && start2<=right){
        if(arr[start]<=arr[start2]){
            tempArray.push_back(arr[start]);
            start++;
        }else{
            tempArray.push_back(arr[start2]);
            start2++;
        }
    }

    while (start <= mid) {
        tempArray.push_back(arr[start]);
        start++;
    }

    while (start2 <= right) {
        tempArray.push_back(arr[start2]);
        start2++;
    }
    for(int i=left;i<=right;i++){
        arr[i] = tempArray[i-left];
    }
}

// Function to recursively divide the array and merge the sorted halves.
void mergeSort(int arr[], int left, int right) {
    if (left >= right)
        return;

    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

// Function to initiate the merge sort process.
void processMergeSort(int arr[], int n) {
    if(n>1){
        mergeSort(arr,0,n-1);
    }
}

void displayArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// Function to dynamically allocate an array and fill it with random values.
void fillDynamicArrayWithRandomValues(int** arr, int* n) {
    cout << "Enter the size of the array: ";
    cin >> *n;
    *arr = new int[*n];
    srand(time(0)); // Seed for random number generation
    for (int i = 0; i < *n; i++) {
        (*arr)[i] = rand() % 1000; // Fill with random numbers between 0 and 999
    }
}

int main() {
    int* arr;
    int n;
    fillDynamicArrayWithRandomValues(&arr, &n);
    cout << "Unsorted array: ";
    displayArray(arr, n);
    processMergeSort(arr, n);
    cout << "Sorted array: ";
    displayArray(arr, n);
    delete[] arr; // Deallocate dynamically allocated memory
    return 0;
}