Recursive Heapsort in C

First, I created a test for your algorithm:

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

Output was as expected: 0 1 2 3 4 5 6 7 8 9 10 . See here working on ideone.

So now we can tweak your code. The first step is to transform the while of the criarHeap function into a recursion.

We see that this while changes the variable filho that will be used after the end of this loop. Thus, the recursive function that will override this while may return the value of that variable. The variables that are used in this while and that are received externally are v , inicio , aux , filho and final , so these become the parameters for the recursive function. >

The code looks like this:

int criarHeapRecursao(int v[], int inicio, int aux, int filho, int final) {
    if (filho > final) return inicio;

    // Pai tem 2 filhos? Se sim, qual é o maior?
    if (filho < final && filho + 1 < final && v[filho] < v[filho + 1]) {
        filho++;
    }

    // Troca o filho com o pai se o filho for maior.
    if (aux < v[filho]) {
        v[inicio] = v[filho];
        inicio = filho;
        filho = 2 * inicio + 1;
    } else {
        filho = final + 1;
    }
    return criarHeapRecursao(v, inicio, aux, filho, final);
}

void criarHeap(int v[], int inicio, int final) {
    int aux = v[inicio];
    int filho = inicio * 2 + 1;
    inicio = criarHeapRecursao(v, inicio, aux, filho, final);
    v[inicio] = aux; // Pai troca com filho mais profundo mais a direita.
}

Notice that the recursion is at the end of the function criarHeapRecursao and what was the stop condition of while became if at the beginning of the function.

Once this is done, we now have the heapSort function that has two loops. Each loop will turn a recursive function apart. The stop condition is set to if at the beginning of the function and the counter becomes one of the parameters of each of these recursive functions. The other variables used in the loops ( v and tam ) also become parameters. The recursive call is placed at the end of each fuction. The result is this:

void heapSort1(int v[], int i, int tam) {
    if (i < 0) return;
    criarHeap(v, i, tam - 1);
    heapSort1(v, i - 1, tam);
}

void heapSort2(int v[], int i, int tam) {
    if (i <= 0) return;
    int aux = v[0];
    v[0] = v[i];
    v[i] = aux;
    criarHeap(v, 0, i - 1); // Cria o heap sem o maior elemento anterior.
    heapSort2(v, i - 1, tam);
}

void heapSort(int v[], int tam) {
    heapSort1(v, (tam - 1) / 2, tam);
    heapSort2(v, tam - 1, tam);
}

In this way, the loops of the heapSort function were converted to the recursive functions heapSort1 and heapSort2 .

The variable aux had a scope where it was used only inside the second loop, but its value was not used between one iteration and another, it did not make sense before the first iteration and was not used after the last iteration. For this reason, it has become a local variable of heapSort2 .

The output remains the expected, 0 1 2 3 4 5 6 7 8 9 10 . See here working on ideone.