Untitled

#include "../include/caller.hpp"

void merge(int p, int q, int r, int *A)
{
        int i,j,k;
        int n1=q-p+1;
        int n2=r-q;
        int *L=new int[n1+1];
        int *R=new int[n2+1];
        for (i=0; i<n1;i++)
                L[i]=A[p+i];
        for (j=0; j<n2;j++)
                R[j]=A[q+j+1];
        L[n1] = abs(L[n1-1]) + abs(R[n2-1]);
        R[n2] = abs(L[n1-1]) + abs(R[n2-1]);
        i=0;
        j=0;
        for (k=p;k<=r;k++)
                if (L[i]<=R[j])
                        A[k]=L[i++];
                else
                        A[k]=R[j++];
        delete L[];
        delete R[];
}

void merge_nat(int *A, int n)
{
int first,i,mid;
        do
        {
                i=0;
                while (i<n-1)
                        {
                                first=i;
                                while(i<n-1 && A[i]<=A[i+1]) i++;
                                mid=i;
                                i++;
                                while(i<n-1 && A[i]<=A[i+1]) i++;
                                if (i<n-1)
                                {
                                        merge(first,mid,i,A);
                                        ++i;
                                }
                        }
        }
        while (first!=0);
}

int main(int argc, char** argv) {

   call_sort(merge_nat);
   return 0;
}