How to implement a Recursive Merge

Question

I have a Mergesort algorithm and I would like to implement the merge function recursively, it is not the recursive Mergesort function but its Merge function. Here is the code for the Merge Function and Merge Sort:

void mergeInt (int v[], int inicio, int fim)
{
  int meio = (inicio + fim) / 2;
  int i = inicio;       
  int j = meio + 1;     

  int tam = fim - inicio + 1;
  int *aux = malloc (sizeof (int) * tam);   

  int k = 0;
  while (i <= meio || j <= fim)
    {
      if (i > meio)
    {           
      aux[k] = v[j];
      j++;
    }
      else if (j > fim)
    {           
      aux[k] = v[i];
      i++;
    }
      else if (v[i] < v[j])
    {           
      aux[k] = v[i];
      i++;
    }
      else
    {           
      aux[k] = v[j];
      j++;
    }

      k++;
    }

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

  free (aux);
}

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

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

      mergeInt (v, inicio, fim);
    }
}

Answer 1

First, I set up 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 here it working on ideone.

Before transforming the mergeInt from iterative to recursive, some changes need to be made to resolve some things that would prevent the recursive version from working:

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

• We remove from inside the mergeInt, the last for which copies of aux for v.

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

The code goes 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 function mergeInt reduced to being little more than just a noose while. So now we can 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 intervals that will be merged into aux and j and fim corresponds to the other range. O k also becomes a parameter to indicate at which point of aux the intercalation between the two intervals is happening.

The code goes 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.