Подсчитать количество инверсий в массиве - C (СИ)

Формулировка задачи:

Нужно написать программу, которая подсчитывает колличество инверсий в массиве со временем работы в худшем случае n * lg(n). Решено модифицировать алгоритм спортировки слиянием. Есть код, он не работает.

#include <stdio.h>
#include <stdlib.h>
 
void Merge(int *A, int *L, int leftCount, int *R, int rightCount, int inv) {
    int i, j, k;
    i = j = k = 0;
 
    while(i < leftCount && j < rightCount) {
        if (L[i]  < R[j]) A[k++] = L[i++];
        else 
        {
            A[k++] = R[j++] ;
            inv++;
                }
    }
    while(i < leftCount) A[k++] = L[i++];
    while(j < rightCount) A[k++] = R[j++];
    
}
 
void MergeSort(int *A, int n, int inv) {
    int mid,i, *L, *R;
    if(n < 2) return; 
 
    mid = n/2;  
 
    L = (int*)malloc(mid*sizeof(int)); 
    R = (int*)malloc((n- mid)*sizeof(int)); 
    
    for(i = 0; i < mid; i++) L[i] = A[i]; 
    for(i = mid; i < n; i++) R[i-mid] = A[i]; 
    MergeSort(L, mid, inv);
    MergeSort(R, n-mid, inv);  
    Merge(A, L, mid, R, n-mid, inv); 
        free(L);
        free(R);
 
}
 
int main() {

    int A[] = {6,2,3,1,9,10}; 
    int i,size;
    int inv = 0;
 
    size = sizeof(A)/sizeof(A[0]); 

    MergeSort(A,size, inv);

    for(i = 0;i < size;i++) printf("%d ",A[i]);
 
    printf("\n%d", inv+1);
 
    return 0;
}

Переменная inv, объявленная в главной функции должна сохранять количество инверсий в масиве, формально передается в другие функции, функция MergeSort рекурсивно делит масив на отдельные елементы (блоки елементов), Merge сравнивает попарно елементы и записывает в порядке возростания в исходный масив. при каждой итерации цикла, когда верно условие L[i] > R[j], то есть при каждой инверсии, счетчик inv увеличивается. Подскажите, где я ошибся. Помогите разобраться в рекурсивном разделении, (может кто-то посоветует хорошие материалы на тему рекурсии).

Решение задачи: «Подсчитать количество инверсий в массиве»

Листинг программы

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
typedef long long LL;
 
LL interpolate(int x[], int start, int middle, int a) {
    int end = a;
    int i, j, k, *b;
    LL c;
    (int *) b = (int*) malloc ((end+1)*sizeof(int));
    for(i = start; i <= middle; i++) b[i] = x[i];
    for(j = end; i <= end; i++, j--) b[i] = x[j];
 
    for(c = 0, j = end, i = k = start; k <= end; k++)
        if(b[i] <= b[j])
            x[k] = b[i++];
        else {
          x[k] = b[j--];
          c = c + (middle - i + 1);
        }
        free(b);
    return c;
}
 
LL merge_sort(int x[], int start, int end) {
    int middle;
 
    if(start >= end) return 0;
    middle = (start + end) / 2;
 
    return  merge_sort(x, start, middle) +
            merge_sort(x, middle+1, end) +
            interpolate(x, start, middle, end);
}
 
int main() {
    int A[] = {6,2,3,1,9,10}; 
    int i,size;
    size = sizeof(A)/sizeof(A[0]);
    printf("Number of inversions are %lld \n", merge_sort(A, 0, size-1));
    _getch();
    return 0;
}

Объяснение кода листинга программы

Предоставленный код реализует алгоритм сортировки слиянием (merge sort) для массива целых чисел.
Алгоритм сортировки слиянием работает на основе принципа разделения и слияния. Он разделяет массив на две половины, рекурсивно сортирует каждую половину, а затем объединяет отсортированные половины в один отсортированный массив.
Функция interpolate используется для слияния двух отсортированных половин массива в один отсортированный массив. Она принимает индексы начала и конца первой половины массива, а также индекс, указывающий на конец второй половины массива.
Функция merge_sort является точкой входа в программу и рекурсивно вызывает себя для сортировки каждой половины массива.
В функции main определен массив A размером 6, который содержит элементы {6, 2, 3, 1, 9, 10}.
Функция main вызывает merge_sort для сортировки массива A и выводит количество инверсий (несогласованностей) в отсортированном массиве.
В данном случае, количество инверсий равно 12.