Merge(int A[], int L, int M, int R)
{
    int *B = new int[R - L + 1];
    int i = L, j = M + 1, k = 0;
    while (i <= M && j <=R)
        if (A[i] <= A[j])
            B[k++] = A[i++];
        else
            B[k++] = A[j++];
    if (i > M)
        for (int p = j; p <= R; p++)
            B[k++] = A[p];
    else
        for (int p = i; p <= M; p++)
            B[k++] = A[p];
    for (k = 0; k < R - L + 1; k++)
        A[L + k] = B[k];
    delete [] B;
}

mergeSort(int A[], int L, int R)
{
    if (L < R)
    {
        int M = (L + R) / 2;
        mergeSort(A, L, M);
        mergeSort(A, M + 1, R);
        Merge(A, L, M, R);
    }
}