Merge Sort

mergesort.c

#include <stdio.h>
#include <stdlib.h>

#define LEN 10000
#define INF 30000 /* Larger than all other elements .*/

// Use "$ time ./mergesort" command to measure execution time.

void merge(int *A, int p, int q, int r) {
    int i, j, k, n1, n2, *L, *R;

    //n1 = ???;
    n1 = q - p;
    //n2 = ???;
    n2 = r - q;
    L = (int *)malloc(n1 * sizeof(int) + 1);
    //R = (int *)malloc(???);
    R = (int *)malloc(n2 * sizeof(int) + 1);

    //for (i = 0; i < ???; i++) {
    for (i = 0; i < n1; i++) {
        //L[i] = A[???];
        L[i] = A[p + i];
    }
    //for (j = 0; j < ???; j++) {
    for (j = 0; j < n2; j++) {
        //R[j] = A[???];
        R[j] = A[q + j];
    }
    i = j = 0;
    L[n1] = R[n2] = INF;
    for (k = p; k < r; k++) {
        if(L[i] <= R[j]) {
            //A[k] = L[???];
            A[k] = L[i];
            i++;
        } else {
            //A[k] = R[???];
            A[k] = R[j];
            j++;
        }
    }
    free(L);
    //free(???);
    free(R);
}

void mergesort(int *A, int p, int r) {
    int q;

    if (r > (p + 1)) {
        q = (p + r) / 2;
        mergesort(A, p, q);
        //mergesort(A, ???, r);
        mergesort(A, q, r);
        //merge(A, p, ???, r);
        merge(A, p, q, r);
    }
}

void sorting_merge(int *A, int n) {
    //mergesort(A, ???, n);
    mergesort(A, 0, n);
}

int main() {
    int i, *n;

    n = malloc(sizeof(int) * LEN);
    // srand(???);
	srand(911);
    for (i = 0; i < LEN; i++) {
        n[i] = rand() % 1000;
        printf("%d ", n[i]);
    }
    printf("\n\n");

    // sorting_merge(n, ???);
    sorting_merge(n, LEN);

    for (i = 0; i < LEN; i++) {
        printf("%d ", n[i]);
    }
    printf("\n");
    // free(???);
    free(n);

    return 1;
}