Я сталкиваюсь с проблемами при вызове рекурсивной функции в сортировке слиянием на языке C

В функции mergeSort есть проблема: вы неправильно вычисляете индекс mid, для среза из 2 элементов mid будет равно right, а вызов mergeSort(a, mid + 1, right) будет иметь неопределенное поведение, потому что mid + 1 > right — условие, которое функция не может обработать.

Вы должны использовать int mid = (left + right) / 2; или лучше:

    int mid = left + (right - left) / 2;  // prevent potential overflow

В функции merge тоже есть проблема: тест elementsMoved < r некорректен, так как r — это индекс последнего элемента, а elementsMoved количество итераций. Нет смысла повторять более r - l + 1 раз, но тест этого не реализует.

Вы используете 2 разных соглашения в своем коде:

• endPos - это индекс после конца среза в void rightCircularShift(int *a, int startPos, int endPos)
• right — индекс последнего элемента среза в void mergeSort(int *a, int left, int right)

Было бы менее запутанно всегда использовать первое соглашение, принятое в C, где индексы массива начинаются с 0.

Кроме того, вы не должны использовать <= в if (a[leftCounter] <= a[rightCounter]), чтобы сделать сортировку стабильной.

Вот модифицированная версия:

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

void rightCircularShift(int *a, int startPos, int endPos) {
    if (startPos < endPos) {
        int temp = a[endPos - 1];
        for (int j = endPos - 1; j > startPos; j--) {
            a[j] = a[j - 1];
        }
        a[startPos] = temp;
    }
}

void merge(int *a, int left, int mid, int right) {
    int leftCounter = left;
    int rightCounter = mid;
    while (leftCounter < mid && rightCounter < right) {
        if (a[leftCounter] <= a[rightCounter]) {
            leftCounter++;
        } else {
            rightCircularShift(a, leftCounter, rightCounter + 1);
            leftCounter++;
            rightCounter++;
            mid++;
        }
    }
}

void mergeSort(int *a, int left, int right) {
    if (right - left > 1) {
        // mid is the index of the first element of the second slice
        int mid = left + (right - left) / 2;
        mergeSort(a, left, mid);
        mergeSort(a, mid, right);
        merge(a, left, mid, right);
    }
}

int main() {
    int n, i, *array;
    system("clear");
    printf("\nEnter number of elements: ");
    if (scanf("%d", &n) != 1 || n <= 0)
        return 1;
    array = malloc(sizeof(*array) * n);
    if (array == NULL)
        return 1;
    printf("Enter value of elements:\n");
    for (i = 0; i < n; i++) {
        if (scanf("%d", &array[i]) != 1)
            return 1;
    }
    printf("\n");
    mergeSort(array, 0, n);
    printf("\n");
    for (i = 0; i < n; i++) {
        printf("%d\t", array[i]);
    }
    printf("\n");
    free(array);
    return 0;
}

Однако обратите внимание, что реализация сортировки слиянием таким образом очень неэффективна: необходимое пространство ограничено O (log (N)), что соответствует глубине рекурсии, но средняя временная сложность увеличивается до O (N2) или хуже, особенно для очень проверенный пример: массив, отсортированный в порядке убывания.

Есть способы реализовать сортировку слиянием с ограниченным объемом памяти, ограничивая при этом этот недостаток, но они более сложны, чем этот простой подход.