MergeSort

Implementazione in Linguaggio C dell’algoritmo MergeSort

#include

typedef int (*compare_ptr)(void** V, int a, int b);

void merge(void** V, int first, int middle, int last, compare_ptr cmp){
int n = last - first + 1;
if(n==1)return;

void** aux = (void**)malloc(n*sizeof(void*));

int lowOne = first;
int lowTwo = middle + 1;
int i = 0;

while(lowOne <= middle && lowTwo <= last){

if( cmp(V,lowOne,lowTwo) )
aux[i] = V[lowTwo++];

else
aux[i] = V[lowOne++];

i++;
}

int k;
if(lowOne <= middle)
for(k=i; k<n; k++)
aux[k] = V[lowOne++];

else if(lowTwo <= last)
for(k=i; k<n; k++)
aux[k] = V[lowTwo++];

for(i=0; i=hi)return;
int m = (lo+hi)/2;

mergesort(V,lo,m,cmp);
mergesort(V,m+1,hi,cmp);
merge(V,lo,m,hi,cmp);

return;
}

Etichette: algoritmi di ordinamento, algoritmo, implementazione, linguaggio c, merge sort, mergesort