"Kevin King" <fr**********@msn.com> wrote in message

news:fb**************************@posting.google.c om...

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

fr**********@msn.com

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[i]=temp[i];

delete [] temp;

}

honestly, I didn't read your code.

but I had the same problem in my assignment, and I figure out that I was

counting all the comparisons.

you have to differentiate, in "merge sort", the DATA comparison and the

INDEX comparison.

index comparisons should not be counted as comparisons.

note also that the numner of moves is always the same whatever is the size

of your array.

coz, when sorting, you copy your whole array to a 'temp' array, and then you

re-copy it, in different order by comparing the indexes(not counted) and

comparing the Data in the array(counted).

i hope that would would help you....

in case you want the implemantation of merge sort (Shaffer Code), i have

ready and modified in a way that counts the number os moves and comparisons.

EliahO_o