#include<iostream>
using namespace std;

void merge(int *arr, int Start, int Mid, int End)
{
    int k = 0;
    int temp[End - Start + 1];
    int i = Start;
    int j = Mid + 1;
    while (i <= Mid && j <= End)
    {
        if (arr[i] < arr[j])
        {
            temp[k] = arr[i];
            k++; i++;
        }
        else
        {
            temp[k] = arr[j];
            k++; j++;
        }
    }
    while (i <= Mid)
    {
        temp[k] = arr[i];
        k++; i++;
    }
    while (j <= End)
    {
        temp[k] = arr[j];
        k++; j++;
    }
    for (i = Start; i <= End; i++)
    {
        arr[i] = temp[i - Start];
    }
}




void mergesort(int *arr, int start, int end)

{
    if (start < end)
    {
        int mid = (start + end) / 2;
        mergesort(arr, start, mid);
        mergesort(arr, mid + 1, end);
        merge(arr, start, mid, end);
    }
}


int main()
{
    int N = 0, i;
    int arr[N];
    cout << "enter the number of elements you wanna take in array" << "\n";
    cin >> N;
    cout << "enter the elements in array" << "\n";
    for (int i = 0; i <= N - 1; i++)
    {
        cin >> arr[i];
    }
    cout << "your array is" << "\n";
    for (int i = 0; i <= N - 1; i++)
    {
        cout << arr[i] << " ";
    }
    cout << "\n";
    mergesort(arr, 0, N - 1);
    for (int i = 0; i <= N - 1; i++)
    {
        cout << arr[i] << " ";
    }
    cout << "\n";

    return 0;

}