I am facing problems while calling recursive function in merge sort in C Language

Question

I basically want to implement merge sort without creating an extra array. But when I call my function recursively gcc gives segmentation fault error Here is my code

Right Circular Shift

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

Merge

void merge(int *a, int l, int r, int m)
{
    int leftCounter = l, elementsMoved = 0;
    int rightCounter = m;
    while (elementsMoved < r) {
        if (leftCounter != r || rightCounter != r) {
            if (a[leftCounter] < a[rightCounter]) {
                leftCounter++;
            } else {
                rightCircularShift(a, leftCounter, rightCounter + 1);
                leftCounter++;
                rightCounter++;
            }
        } else {
            break;
        }
        elementsMoved++;
    }
}

Main

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

Merge Sort

void mergeSort(int *a, int left, int right)
{
    int mid = (left + right + 1) / 2;
    if (left < right) { 
        mergeSort(a, left, mid);
        mergeSort(a, mid + 1, right);
        merge(a, left, right, mid);
    }   
}

I have ensured the rest of the functions like circular shift and merge are working properly with test cases, but I get this error:

Answer 1

There is a problem in the mergeSort function: you compute the mid index incorrectly, for a slice of 2 elements, mid will be equal to right and the call mergeSort(a, mid + 1, right) will have undefined behavior because mid + 1 > right, a condition the function cannot handle.

You should use int mid = (left + right) / 2; or better:

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

There is also a problem in the merge function: the test elementsMoved < r is incorrect as r is the index of the last element and elementsMoved the number of iterations. It does not make sense to iterate more than r - l + 1 times, but the test does not implement that.

You use 2 different conventions in your code:

• endPos is the index past the end of the slice in void rightCircularShift(int *a, int startPos, int endPos)
• right is the index of the last element of the slice in void mergeSort(int *a, int left, int right)

It would be less confusing to always use the first convention, which is customary in C, where array indexes start at 0.

Also not that you must use <= in if (a[leftCounter] <= a[rightCounter]) to make the sort stable.

Here is a modified version:

#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;
}

Note however that implementing merge sort this way is very inefficient: the space needed is limited to O(log(N)), corresponding to the recursion depth, but the average time complexity explodes to O(N²) or worse, especially for the very example tested: an array sorted in decreasing order.

There are ways to implement merge sort with limited amount of memory while limiting this downside, but they are more complicated than this simple approach.