// Merge Sort example
// For input array
// 2 8 7 1 3 5 6 4 9 0
//
// First partion in L[] and R[] will be
// L[] = 2 8 7 1 3 ==> L[] = 2 8 7 | R[] = 1 3 ==> L[] = 2 8 | R[] = 7
// R[] = 5 6 4 9 0
//
#include <stdio.h>

#define EOA 100000  //End of array

// To enable debug messages uncomment #define
// #define DEBUG 1

#ifdef DEBUG
#  define D(x) x
#else
#  define D(x)
#endif

void mergesort(int arr[], int p, int r); 
void merge(int arr[], int p, int q, int r); 

int arr[10] = {2, 8, 7, 1, 3, 5, 6, 4, 9, 0}; 

int main()
{
    int i = 0;
    printf("Input array\n");
    for (i = 0; i <= 9; i++) {
        printf("%d ", arr[i]);
    }   
    printf("\n\n");

    mergesort(arr, 0, 9); 

    printf("Sorted output\n");
    for (i = 0; i <= 9; i++) {
        printf("%d ", arr[i]);
    }   
    printf("\n");
    
    return 0;
}

void mergesort(int arr[], int p, int r)
{
    if (p < r) {
        int q = (p + r) / 2;

        mergesort(arr, p, q);
        mergesort(arr, q+1, r);
        merge(arr, p, q, r);
    }
}

void merge(int arr[], int p, int q, int r)
{
    int n1 = q - p + 1;
    int n2 = r - q;
    int i = 0;
    int j = 0;

    int L[15];
    int R[15];

    //Copy elements from p to n1 in L[]
    for (i = 0; i < n1; i++) {
        L[i] = arr[p + i];
    }
    L[i] = EOA;

    for (j = 0; j < n2; j++) {
        R[j] = arr[q + j + 1];
    }
    R[j] = EOA;

    int lindx = 0;
    int rindx = 0;
    //Merge array L[] and R[]
    for (i = p; i <= r; i++) {
        if(L[lindx] <= R[rindx]) {
            arr[i] = L[lindx++];
        } else {
            arr[i] = R[rindx++];
        }
    }

    // Print debug statements
    D(printf("\n######################\n"));
    D(printf("Left array\n"));

    for (i = 0; i < n1; i++) {
        D(printf("%d ", L[i]));
    }

    D(printf("\nRight array\n"));
    for (i = 0; i < n2; i++) {
        D(printf("%d ", R[i]));
    }

    D(printf("\nAfter Merge\n"));
    for (i = p; i <= r; i++) {
        D(printf("%d ", arr[i]));
    }
    D(printf("\n\n"));
}