#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 10

int main(void)
{
    srand(time(NULL));
    int A[N];
    for(int i = 0; i < N; i++){
        A[i] = rand()%100;
    }

    PrintArray(A,N);
    RecursiveMergeSort(A,0,N-1);
    PrintArray(A,N);

    return 0;
}

void RecursiveMergeSort(int *A, int p, int r){
    if(p < r){
        int q = (p+r)/2;
        RecursiveMergeSort(A,p,q);
        RecursiveMergeSort(A,q+1,r);
        RecursiveMerge(A,p,q,r);
    }
}

void RecursiveMerge(int *A, int p, int q, int r){
    int a = q-p;
    int b = r-q+1;
    int L[a+1], R[b+1];
    for(int i = 0; i < a; i++){
        L[i] = A[p+i];
    }
    for(int j = 0; j < b; j++){
        R[j] = A[q+j-1];
    }
    L[a+1] = 10000;
    R[b+1] = 10000;
    int i = 0;
    int j = 0;
    for(int k = p; k < r; k++){
        if(L[i] < R[j]){
            A[k] = L[i];
            i++;
        } else {
            A[k] = R[j];
            j++;
        }
    }
}