merge sort help

[mqueene7]

below is my code for my merge sort but I can't get it to sort properly. I am trying generate random numbers based on input from the user and then sort those random numbers. Can you tell me what I am doing wrong?

[CODE=cpp]
void merge(int,int,i nt);
void merge_sort(int low, int high)
{
int mid, temp;
if (low==high)
return;
if (low+1==high)
{
temp=high;
high=low;
low=temp;
}
if(low<high)
{
mid=(low+high)/2;
merge_sort(low, mid);
merge_sort(mid+ 1,high);
merge(low,mid,h igh);
}
}
void merge(int low,int mid,int high)
{
int p, q, i, c[10],r;
p=low; //index for a[i]...a[mid]
q=mid+1; //index for a[mid + 1]...a[j]
while((p<=mid)& &(q<=high))
{
if(a[p]<=a[q]) //copy smaller value to local array c
{
c[i]=a[p];
p++;
}
else
{
c[i]=a[q];
q++;
}
i++;
}
while (a[p]<= mid)//copy the rest of the longer array
{
c[i] = a[p];
}
while (a[q]<=high)//copy the rest of the larger array
{
c[i]=a[q];
}
for (i=low; i<=high; i++)//copy back from temp array to main array
{
a[i]=c[i];
}
}

int main()
{
long timeElapsed;
timeElapsed = clock();
int num,i,elem, percent;
a[num];
cout<<"******** *************** *************** *************** *************** *"<<endl;
cout<<" MERGE SORT PROGRAM"<<endl;
cout<<"******** *************** *************** *************** *************** **"<<endl<<endl <<endl;
cout<<"Please Enter THE NUMBER OF ELEMENTS you want to sort[THEN PRESS ENTER]:"<<endl;
cin>>num;
cout<<"Please Enter THE PERCENTAGE you want to sort[THEN PRESS ENTER]:"<<endl;
cin>>percent;
for (i=1; i<=num; i++)
{
elem =((rand()*9)+1) ;
cout<<endl<<"el ement "<<i<<"is "<<elem<<en dl;
a[i]= elem;
cout<<"When i is "<<i<<" ai is "<<a[i];
}
merge_sort(1,nu m);
cout<<endl<<"So , the sorted list (using MERGE SORT) will be : "<<endl;
for(i=1;i<=num; i++)
{
cout<<a[i]<<" ";
}
cout<<endl<<"Ti me Elapsed is: "<<timeElapsed< <endl<<endl<<en dl<<endl<<endl;
system("PAUSE") ;
return 0;
}[/CODE]

[gpraghuram]

Hi,
There are couple of issues in the code....
1)First u start referencing the array from 1 and reach the max size which is wrong(For example if size of array is 5 then in the loop u shuld start from 0 and reference upto 4)
2)U are not initializing local variables before usage.

I have corrected some part of the code and posted it here....
[code=cpp]
void merge(int,int,i nt);
void merge_sort(int low, int high)
{
int mid, temp;
if (low==high)
return;
if (low+1==high)
{
temp=high;
high=low;
low=temp;
}
if(low<high)
{
mid=(low+high)/2;
merge_sort(low, mid);
merge_sort(mid+ 1,high);
merge(low,mid,h igh);
}
}
void merge(int low,int mid,int high)
{
int p, q, i, c[10],r;
i=0;
r=0;
p=low; //index for a[i]...a[mid]
q=mid+1; //index for a[mid + 1]...a[j]
while((p<=mid)& &(q<=high))
{
if(a[p]<=a[q]) //copy smaller value to local array c
{
c[i]=a[p];
p++;
}
else
{
c[i]=a[q];
q++;
}
i++;
}
while (a[p]<= mid)//copy the rest of the longer array
{
c[i] = a[p];
}
while (a[q]<=high)//copy the rest of the larger array
{
c[i]=a[q];
}
for (i=low; i<=high; i++)//copy back from temp array to main array
{
a[i]=c[i];
}
}

int main()
{
long timeElapsed;
timeElapsed = clock();
int num,i,elem, percent;
//a[num];
cout<<"******** *************** *************** ************ *************** ****"<<endl;
cout<<" MERGE SORT PROGRAM"<<endl;
cout<<"******** *************** *************** ************ *************** *****"<<endl<<e ndl<<endl;
cout<<"Please Enter THE NUMBER OF ELEMENTS you want to sort[THEN PRESS ENTER]:"<<endl;
cin>>num;
cout<<"Please Enter THE PERCENTAGE you want to sort[THEN PRESS ENTER]:"<<endl;
cin>>percent;
//for (i=1; i<=num; i++)
for (i=0; i<num; i++)
{
elem =((rand()*9)+1) ;
cout<<endl<<"el ement "<<i<<"is "<<elem<<en dl;
a[i]= elem;
cout<<"When i is "<<i<<" ai is "<<a[i];
}
//merge_sort(1,nu m);
merge_sort(0,nu m);
cout<<endl<<"So , the sorted list (using MERGE SORT) will be : "<<endl;
//for(i=1;i<=num; i++)
for(i=0;i<num;i ++)
{
cout<<a[i]<<" ";
}
cout<<endl<<"Ti me Elapsed is: "<<timeElapsed< <endl<<endl<<en dl<<endl<<endl;
system("PAUSE") ;
return 0;
}

[/code]

Try this....i havent checked the logic of ur code still...
Raghuram

[mqueene7]

<Sometimes posting with a quote and code causes the post to disappear. The quote has been removed so that the response is visible.

MODERATOR>

I tried this and it looks good, but my sort isn't sorting correctly. Can you you look at the logic? Thank you!!