K
Kevin King
I have a question about an assignment I have. I need to count the
number of comparisons in my merge sort. I know that the function is
roughly nlog(n), but I am definately coming up with too many
comparisons. It seems to me like I should just use a single counter in
the merge function's 'if' statement, but this can't be right because
an array of 50 takes about 100 comparisons this way. If anyone has any
suggestions I would greatly appreciate it.
-Kevin
(e-mail address removed)
void mergeSort(int data[], int size)
{
int n1,n2;
if(size>1)
{
n1=size/2;
n2=size-n1;
mergeSort(data,n1);
mergeSort((data+n1),n2);
merge(data, n1,n2);
}
}
void merge(int data[], int n1, int n2)
{
int *temp;
int copied=0;
int copied1=0;
int copied2=0;
int i;
temp=new int[n1+n2];
while((copied1<n1) &&(copied2<n2))
{
if(data[copied1]<(data+n1)[copied2])
temp[copied++]=data[copied1++];
else
temp[copied++]=(data+n1)[copied2++];
}
while(copied1<n1)
temp[copied++]=data[copied1++];
while(copied2<n2)
temp[copied++]=(data+n1)[copied2++];
for(i=0;i<n1+n2;i++)
data=temp;
delete [] temp;
}
number of comparisons in my merge sort. I know that the function is
roughly nlog(n), but I am definately coming up with too many
comparisons. It seems to me like I should just use a single counter in
the merge function's 'if' statement, but this can't be right because
an array of 50 takes about 100 comparisons this way. If anyone has any
suggestions I would greatly appreciate it.
-Kevin
(e-mail address removed)
void mergeSort(int data[], int size)
{
int n1,n2;
if(size>1)
{
n1=size/2;
n2=size-n1;
mergeSort(data,n1);
mergeSort((data+n1),n2);
merge(data, n1,n2);
}
}
void merge(int data[], int n1, int n2)
{
int *temp;
int copied=0;
int copied1=0;
int copied2=0;
int i;
temp=new int[n1+n2];
while((copied1<n1) &&(copied2<n2))
{
if(data[copied1]<(data+n1)[copied2])
temp[copied++]=data[copied1++];
else
temp[copied++]=(data+n1)[copied2++];
}
while(copied1<n1)
temp[copied++]=data[copied1++];
while(copied2<n2)
temp[copied++]=(data+n1)[copied2++];
for(i=0;i<n1+n2;i++)
data=temp;
delete [] temp;
}