#include<bits/stdc++.h>
using namespace std;

void Merge(int arr[],int start,int mid, int end)
{

    int n1=mid-start+1; /// size of left array
    int n2=end-mid; /// size of right array
    int L[n1],R[n2];



    for(int i=0; i<n1; i++)
    {

        L[i]=arr[start+i];
    }

    for(int i=0; i<n2; i++)
    {

        R[i]=arr[mid+1+i];
    }

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


}

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 arr[]= {21,3,54,-45,78,2,-1};
    int n= sizeof(arr)/sizeof(arr[0]);

    mergeSort(arr,0,n-1);

    cout<<"after sorting in descendig order: ";
    for(int i=n-1; i>=0; i--)
    {
        cout<<arr[i]<<" ";
    }
    cout<<endl;
    cout<<"after sorting in ascending order: ";
    for(int i=0; i<n; i++)
    {
        cout<<arr[i]<<" ";
    }
    return 0;
}