How to implement a generic Mergesort sorting algorithm?

Question

How to implement an sorting algorithm Mergesort generic (with function pointer and pointer void) in that capacity?

#include<stdio.h>
typedef struct{
    inta;
    intb;
}XPTO;

void criaVetor(XPTO∗v, int n){
    int i;
    for(i=0;i<n;i++){
    v[i].a=i%3;
    v[i].b=100−i%5;
    }
}


void imprimeVetor(XPTO∗v, int n){
    int i;
    for(i=0;i<n;i++){
    printf(”a=%d b=%d\n”,v[i].a,v[i].b);
    }
}

int porA(void ∗p1,void ∗p2){
    XPTO∗pp1=p1;
    XPTO∗pp2=p2;
    return pp1−>a < pp2−>a;
}

int porB(void ∗p1,void ∗p2){
    XPTO∗pp1=p1;
    1XPTO∗pp2=p2;
        returnpp1−>b < pp2−>b;
}


int main(int argc,char∗ argv[]){ 

XPTO v[10];
criaVetor(v,10);

ordena(v,sizeof(XPTO),10,porA);//<−exemplo de chamada da funcao ordena

imprimeVetor(v,10);

return 0;
}

Answer 1

I made a solution below.

1. I used a function pointer to be the comparator (int (*comparador)(void *, void *)). This compared can return a negative number if the first parameter (the first void *) is less than the second, positive if greater, or zero if equal.

2. mergesort requires an auxiliary memory. For this reason, there is a malloc and a free in the implementation of mergesort below. That malloc is performed only once and the same auxiliary memory is used in all recursions of the mergesort_aux. The function mergesort_aux is the one that actually mergesort, just taking as parameter, the auxiliary memory.

3. The function memcpy is used to copy from the array to auxiliary memory and back again. This is used in the intercalation process of the two halves of the array. The intercalation occurs by copying the elements of each half of the array into auxiliary memory, in the order of the elements given by the comparator as determined by the mergesort algorithm. Thus, the function intercalar will put on array aux the intercalation of array1 and array2, using memcpy to copy the elements. With another memcpy the intercalated array is copied back over the two original arrays by overwriting them.

4. Although the function mergesort and the comparator work with elements of the type void *, internally the char * is used. The reason for this is that it is not possible to perform pointer arithmetic with void *. On the other hand, with char *, it is possible to address any byte individually in the array to be ordered.

5. I also put a field c in his XPTO with the original position in the array. This serves to highlight that the ordering of the mergesort is stable. That is, elements that the comparator says are equal are kept in the same order they were in the original array.

Here’s the code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h> // Para a função memcpy

// Código do mergesort:

void intercalar(
    char *array1,
    char *array2,
    size_t tamanho_array1,
    size_t tamanho_array2,
    char *aux,
    size_t tamanho_elemento,
    int (* comparador)(void *, void *)
) {
    int a = 0, b = 0, c = 0;
    while (a < tamanho_array1 || b < tamanho_array2) {
        int ain = a < tamanho_array1;
        int bin = b < tamanho_array2;
        char *e1 = ain ? &array1[a * tamanho_elemento] : NULL;
        char *e2 = bin ? &array2[b * tamanho_elemento] : NULL;
        char *e3 = &aux[c * tamanho_elemento];
        char *comp = (e2 == NULL || (e1 != NULL && comparador(e1, e2) <= 0)) ? e1 : e2;
        memcpy(e3, comp, tamanho_elemento);
        if (comp == e1) a++; else b++;
        c++;
    }
}

void mergesort_aux(
    char *array,
    char *aux,
    size_t tamanho_elemento,
    size_t tamanho_array,
    int (* comparador)(void *, void *)
) {
    if (tamanho_array < 2) return;
    int metade1 = tamanho_array / 2;
    int metade2 = tamanho_array - metade1;
    mergesort_aux(array, aux, tamanho_elemento, metade1, comparador);
    char *temp = &array[metade1 * tamanho_elemento];
    mergesort_aux(temp, aux, tamanho_elemento, metade2, comparador);
    intercalar(array, temp, metade1, metade2, aux, tamanho_elemento, comparador);
    memcpy(array, aux, tamanho_elemento * tamanho_array);
}

void mergesort(
    void *array,
    size_t tamanho_elemento,
    size_t tamanho_array,
    int (* comparador)(void *, void *)
) {
    void *aux = malloc(tamanho_elemento * tamanho_array);
    mergesort_aux((char *) array, (char *) aux, tamanho_elemento, tamanho_array, comparador);
    free(aux);
}

// Seu código de teste:

typedef struct {
    int a;
    int b;
    int c;
} XPTO;

void criar_vetor(XPTO *v, int n) {
    for (int i = 0; i < n; i++) {
        v[i].a = (i % 3) + 4;
        v[i].b = 100 - i % 5;
        v[i].c = i;
    }
}

void imprimir_vetor(XPTO *v, int n) {
    for (int i = 0; i < n; i++) {
        printf("(a=%d b=%d c=%d) ", v[i].a, v[i].b, v[i].c);
    }
    printf("\n");
}

int por_a(void *p1, void *p2) {
    XPTO *pp1 = (XPTO *) p1;
    XPTO *pp2 = (XPTO *) p2;
    return pp1->a - pp2->a;
}

int por_b(void *p1, void *p2) {
    XPTO *pp1 = (XPTO *) p1;
    XPTO *pp2 = (XPTO *) p2;
    return pp1->b - pp2->b;
}

#define T 20

int main(int argc, char* argv[]) {
    XPTO v[T];
    criar_vetor(v, T);

    printf("Antes:\n");
    imprimir_vetor(v, T);

    printf("\nPor A:\n");
    mergesort(v, sizeof(XPTO), T, por_a);
    imprimir_vetor(v, T);

    criar_vetor(v, T); // Recria o vetor.
    printf("\nPor B:\n");
    mergesort(v, sizeof(XPTO), T, por_b);
    imprimir_vetor(v, T);

    return 0;
}

See here working on ideone.