//C program for 
//sorting array
//using Merge Sort
#include <stdio.h>

void merge(int arr[],int l,int m,int r)
{
    int i,j,k;
    int n1=m-l+1;
    int n2=r-m;

//Create temperary arrays
    int L[n1] , R[n2];

    //Copy data to arrays from L[] and R[]
    for(i=0;i<n1;i++)
        L[i]=arr[l+i];
    for(j=0;j<n2;j++)
        R[j]=arr[m+1+j];

    //Initial index of first,second
    //and merged subarray respectively
    i=0;
    j=0;
    k=l;
    while (i<n1 && j<n2){
        if(L[i] <= R[j]){
            arr[k]=L[i];
            i++;
        }
        else{
            arr[k]=R[j];
            j++;
        }
        k++;
    }
    
//Copy the remaining elements of L[]
    while(i<n1){
        arr[k]=L[i];
        i++;
        k++;
   }

    //Copy the remaining elements of R[]
    while(j<n2) {
        arr[k]=R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[],int l,int r)
{
    if(l<r){

        //calculating middle term
        int mid=l+(r-l)/2;

        //divide to sort both halves
        mergeSort(arr,l,mid);
        mergeSort(arr,mid+1,r);

        merge(arr,l,mid,r);
    }
}

int main() 
{
    int arr[]={23,9,13,15,6,7};
    int n=sizeof(arr)/sizeof(arr[0]);

    //Print the original Array
    printf("Given array:");
    for(int i=0;i<n;i++)
        printf(" %d",arr[i]);
    printf("\n");

    mergeSort(arr,0,n-1);

    //Print the Sorted Array
    printf("Sorted array:");
    for(int i=0;i<n;i++)
        printf(" %d",arr[i]);
    printf("\n");

    return 0;
}