#include <iostream>
using namespace std;

void merge(int* A, int p, int q, int r) {       // MERGE(A,p,q,r)
    int n1 = q-p+1;                             //   1. n1 = q-p+1
    int n2 = r-q;                               //   2. n2 = r-q 

    int i,j,k;
    int *L=new int[n1+1], *R = new int[n2+1];   //   3. let L[1...n1+1] and R[1..n2+1] be new arrays

    for(i=0; i<n1; i++)                         //   4. for i = 1 to n1
        L[i]=A[p+i];                            //   5.    L[i] = A[p+i-1]

    for(j=0; j<n2;j++)                          //   6. for j = 1 to n2
        R[j]=A[q+j+1];                            //   7.    R[j] = A[q+j]

    L[n1]=999; //sentinel                       //   8. L[n1+1]= ∞
    R[n2]=999; //sentinel                       //   9. R[n2+1]= ∞
    i=0;                                        //  10. i = 1
    j=0;                                        //  11. j = 1
    for(k=p; k<=r; k++) {                        //  12. for k = p to r 
        if(L[i]<=R[j])                          //  13.    if(L[i]<=R[j])
            A[k]=L[i++];                        //  14.         A[k] = L[i]
                                                //  15.         i = i+1
        else                                    //  16.    else A[k] = R[j]
            A[k]=R[j++];                        //  17.         j = j+1                 
    }
}

void mergeSort(int* a, int p, int r) {        // MERGE-SORT (A,p,r)
    if(p<r) {                                 //  1. if p<r 
        int q=(p+r)/2;                        //  2.   q = (p+r)/2 
        mergeSort(a,p,q);                     //  3.   MERGE-SORT(A,p,q)
        mergeSort(a,q+1,r);                   //  4.   MERGE-SORT(A,q+1,r)
        merge(a,p,q,r);                       //  5.   MERGE(A,p,q,r)
    }
}

int main() {
    int arr[]={5,4,3,2,1};
    mergeSort(arr,0,4);

    for(int i=0; i<5; i++)
        cout << arr[i]<<" ";
}