/******************************************************************************
Online C Compiler.
Code, Compile, Run and Debug C program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <stdio.h>
#include <limits.h>
#include <math.h>
void merge(int A[], int p, int q, int r) {
int n1 = q-p+1;
int n2 = r-q;
int L[n1];
int R[n2];
for(int i = 0; i < n1; ++i) {
L[i] = A[p+i];
}
for(int j =0; j < n2; ++j) {
R[j] = A[q+j+1];
}
L[n1] = INT_MAX;
R[n2] = INT_MAX;
int i = 0;
int j = 0;
for(int k = p; k <= r; ++k) {
if(L[i] <= R[j]) {
A[k] = L[i];
i = i+1;
} else {
A[k] = R[j];
j = j+1;
}
}
}
void merge_recurse(int A[], int p, int r) {
if(p < r) {
int q = floor((p+r)/2);
merge_recurse(A, p, q);
merge_recurse(A, q+1, r);
merge(A, p, q, r);
}
}
void merge_sort(int A[], size_t length) {
merge_recurse(A, 0, (int)length-1);
}
int main()
{
int length = 9;
int A[] = {3, 7, 61, 3, 40, 4, -1, 8, 10};
merge_sort(A, length);
for (int i = 0; i < length; ++i) {
printf("%i, ", A[i]);
}
return 0;
}
