How to implement a Recursive Merge

First, I ran a test for your code:

void mergeSort(int v[], int tamanho) {
    mergeSortInt(v, 0, tamanho);
}

int main() {
    int a[] = {10, 2, 7, 1, 4, 9, 3, 8, 0, 5, 6};
    mergeSort(a, 11);
    for (int i = 0; i < 11; i++) {
        printf("%d ", a[i]);
    }
}

See it working here.

Before turning the mergeInt from iterative to recursive, you need to make some changes to resolve some things that would prevent the recursive version from working:

• Attack your malloc and free . Even in the iterative version, using a lot of malloc s and free s is somewhat inefficient, it would be better to use only one in the entire mergesort process.

• We remove from the mergeInt , the last for that copies from aux to v .

• Within while , we change the if to have only two possible paths instead of four.

The code looks like this:

void mergeInt(int v[], int inicio, int fim, int aux[]) {
    int meio = (inicio + fim) / 2;
    int i = inicio;
    int j = meio + 1;
    int k = 0;
    while (i <= meio || j <= fim) {
        if (i <= meio && (j > fim || v[i] < v[j])) {
            aux[k] = v[i];
            i++;
        } else {
            aux[k] = v[j];
            j++;
        }
        k++;
    }
}

void mergeSortInt(int v[], int inicio, int fim, int aux[]) {
    int meio = (inicio + fim) / 2;

    if (inicio < fim) {
        mergeSortInt(v, inicio, meio, aux);
        mergeSortInt(v, meio + 1, fim, aux);
        mergeInt(v, inicio, fim, aux);

        for (int l = 0; l < fim - inicio + 1; l++) {
            v[inicio + l] = aux[l];
        }
    }
}

void mergeSort(int v[], int tamanho) {
    int *aux = malloc(sizeof(int) * tamanho);
    mergeSortInt(v, 0, tamanho, aux);
    free(aux);
}

int main() {
    int a[] = {10, 2, 7, 1, 4, 9, 3, 8, 0, 5, 6};
    mergeSort(a, 11);
    for (int i = 0; i < 11; i++) {
        printf("%d ", a[i]);
    }
}

See here working on ideone.

At this point, note that the mergeInt function has been reduced to being little more than just a while loop. That way, we can now make it recursive.

The parameters inicio and fim are exchanged for i , meio , j and fim . The logic is that i and meio correspond to one of the ranges that will be merged into aux and j and fim corresponds to the other range. The k also becomes a parameter to indicate at which point of aux the interleaving between the two ranges is happening.

The code looks like this:

void mergeInt(int v[], int i, int meio, int j, int fim, int k, int aux[]) {
    if (i <= meio && (j > fim || v[i] < v[j])) {
        aux[k] = v[i];
        mergeInt(v, i + 1, meio, j, fim, k + 1, aux);
    } else if (j <= fim) {
        aux[k] = v[j];
        mergeInt(v, i, meio, j + 1, fim, k + 1, aux);
    }
}

void mergeSortInt(int v[], int inicio, int fim, int aux[]) {
    int meio = (inicio + fim) / 2;

    if (inicio < fim) {
        mergeSortInt(v, inicio, meio, aux);
        mergeSortInt(v, meio + 1, fim, aux);
        mergeInt(v, inicio, meio, meio + 1, fim, 0, aux);

        for (int l = 0; l < fim - inicio + 1; l++) {
            v[inicio + l] = aux[l];
        }
    }
}

void mergeSort(int v[], int tamanho) {
    int *aux = malloc(sizeof(int) * tamanho);
    mergeSortInt(v, 0, tamanho, aux);
    free(aux);
}

int main() {
    int a[] = {10, 2, 7, 1, 4, 9, 3, 8, 0, 5, 6};
    mergeSort(a, 11);
    for (int i = 0; i < 11; i++) {
        printf("%d ", a[i]);
    }
}

See here working on ideone.