Fiz uma solução abaixo.
Utilizei um ponteiro de função para ser o comparador (int (*comparador)(void *, void *)
). Esse comparado pode retornar um número negativo se o primeiro parâmetro (o primeiro void *
) for menor que o segundo, positivo se for maior, ou zero se forem iguais.
O mergesort necessita de uma memória auxiliar. Por esse motivo, que há um malloc
e um free
na implementação do mergesort
abaixo. Esse malloc
só é efetuado uma vez e a mesma memória auxiliar é usada em todas as recursões do mergesort_aux
. A função mergesort_aux
é a que realiza o mergesort de fato, apenas recebendo como parâmetro, a memória auxiliar.
A função memcpy
é utilizada para copiar do array para a memória auxiliar e de volta também. Isso é usado no processo de intercalação das duas metades do array. A intercalação ocorre ao copiar-se os elementos de cada metade do array na memória auxiliar, na ordem dos elementos dada pelo comparador tal como determina o algoritmo de mergesort. Assim, a função intercalar
vai colocar no array aux
a intercalação de array1
e array2
, usando memcpy
para copiar os elementos. Com um outro memcpy
o array intercalado é copiado de volta por cima dos dois arrays originais sobreescrevendo-os.
Embora a função mergesort
e o comparador trabalhem com elementos do tipo void *
, internamente o char *
é usado. O motivo disso é que não é possível realizar-se aritmética de ponteiros com void *
. Por outro lado, com char *
, é possível endereçar-se qualquer byte individualmente no array a ser ordenado.
Também coloquei um campo c
no seu XPTO
com a posição original no array. Isso serve para evidenciar que a ordenação do mergesort
é estável. Ou seja, elementos que o comparador diz que são iguais são mantidos na mesma ordem em que estavam no array original.
Eis o código:
#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;
}
Veja aqui funcionando no ideone.