Apr 19, 2011

sort an array using mergesort

void merge_sort(int* u, int size)
{
if(size==1)
{
return;
}
//divide the array into 2
//sort each
merge_sort(u, size/2);
merge_sort(u+(size/2), size-(size/2));

int* t=(int*)malloc(sizeof(int)*(size));

for(int i=0,anext=0,bnext=0; i< size; i++)
{
if(anext==size/2)
{
t[i] = *(u+(size/2)+bnext);
bnext++;
}
else if(bnext == size-(size/2))
{
t[i] = *(u+anext);
anext++;
}
else
{
if(*(u+anext) < *(u+(size/2)+bnext))
{
t[i] = *(u+anext);
anext++;
}
else
{

t[i] = *(u+(size/2)+bnext);
bnext++;
}
}
}

//copy back to org array
for(int i=0;i< size;i++)
{
*(u+i) = *(t+i);
}


delete t;
}

No comments: