#include <stdio.h>

#define INFINITY 999999

#define LEN(A) ((sizeof (A)) / (sizeof A[0]))

void print_array(int A[], int len)

{

    int i;

    /*

    int len = LEN(A);

    sizeof on array function parameter will return size of 'int *' instead of 'int []'

      [-Wsizeof-array-argument]

        int len = LEN(A);

                  ^

    */

    for (i = 0; i < len; i++)

        printf("%d, ", A[i]);

    putchar('\n');

}

//merge将本次合并的两个array分别打印

void merge(int A[], int p, int q, int r)

{

    int k, i, j;

    int n1 = q - p + 1;

    int n2 = r - q;

    int L[n1+1], R[n2+1];

    for (i = 0; i < n1; i++)

        L[i] = A[p+i];

    L[n1] = INFINITY;

    print_array(L, n1+1);

    for (j = 0; j < n2; j++)

        R[j] = A[q+1+j];

    R[n2] = INFINITY;

    print_array(R, n2+1);

    i = j = 0;

    for (k = p; k <= r; k++) {

        if (L[i] <= R[j]) {

            A[k] = L[i];

            i++;

        } else {

            A[k] = R[j];

            j++;

        }

    }

}

void mergeSort(int A[], int p, int r)

{

    if (p < r) {

        int q = (p+r)/2;

        mergeSort(A, p, q);

        mergeSort(A, q+1, r);

        merge(A, p, q, r);

    }

}

int main(int argc, char *argv[])

{

    int A[] = {5, 6, 7, 8, 9, 10, 11, 12, 12, -3, 1, 2, 3, 4};

    merge(A, 0, 8, 13);

    print_array(A, LEN(A));

    int B[] = {2, 4, 5, 7, 1, 3, 2, 6};

    mergeSort(B, 0, LEN(B)-1);

    print_array(B, LEN(B));

    return 0;

}