Merg sort

[zeroblank]

i did exactly what the pseudo code told me in the book introduction to algorithms and it didn't work

there are three parts that i dont really understand
1-how do u make a recursive function that is a void i mean shouldnt a recursive function always return the last step then what is before it .. it's a void so how would it preform the task

2-merg_sor() was called twice in one function .. do u call that nested recursion ?or what ?? .. and how does it affect the merg function

3-where is the base case in this recursive function Merg_sort()

 #include <iostream>
#include <vector>

using namespace std;
void Merg(vector<int> Arr,int start,int middle,int end) 
{
	std::vector<int> left;
	std::vector<int> right;
	for(int i =start;i<(end-start);i++)
	{
		if (i <middle)
		{
			right.push_back(Arr.at(i));
		}
		else
		{
			left.push_back(Arr.at(i));
		}
	}
	int j=0;
	int k=0;
	for(int i =start;i<(end-start);i++)
	{
		if(right.at(j)<=Arr.at(i))
		{
			Arr.at(i)=right.at(j);
			j++;
		}
		else
		{
			Arr.at(i)=left.at(k);
			k++;
		}
	}
}
void Merg_sort(vector<int> Arr,int start,int end)
{
	if (start <end)
	{
		int middle = (start+end)/2;
		Merg_sort(Arr,start,middle); 
		Merg_sort(Arr,middle+1,end); 
		Merg(Arr,start,middle,end);
	}
}

int main()
{
 vector<int> x;
 for (int i =0;i<8;i++){x.push_back(i);}
 x.at(2)=8;
 Merg_sort(x,0,7);
}

[Handy Andy]

Hello zeroblank,


As to point 1: most recursive functions that I have seen do return a value, but you could write a recursive function that is void by passing one or more of the arguments as a reference. Thus this should change the value of the variable where the function was called from.

Point 2: do u call that nested recursion ?or what ??. I would call that the "or what" i.e., an endless loop because there is no way out of the recursion. Since the "Merge_sort functions defines an int before it calls itself eventually the endless loop will run out of memory.

Point 3: not sure what you mean y "base case" unless you mean a way out of the loop.

In the function "Merge_sort" the "Merge" function will never be called because of the endless loop that happens before that line. And the name "Merge_sort" is a bit misleading because nothing is ever merged or sorted there.

Some things I will point out in the "Merge" function. Arr is passed to the function by value, so you are only working with a copy of the "Arr" vector which will be lost when the function ends. Passing the vector by reference would be a better choice.

On line 9 and 22 you say i < (end - start); bad form it is hard to understand what you mean and if "start" is anything > 0 your loop will be shorter than what you need. You should either use i < end; or i < Arr.size(); with the latter being more descriptive of what you want to do. I am not sure what the second for loop is fore, but I lean towards the possibility it will not work. Now I say that not having tested it yet to see what it will do.

Hope that helps and gives you some ideas,

Andy

[zeroblank]

heyy Andy,

thanks for the great explination .
however, in merge_sort() ... why is it endless? . u see if (start <end) will make it end because each loop would decrease either the end or the beginning so the last call would be return an emty func of merg_sort.

in merge() function i did that on purpose because in merge sort algorithm u sort parts of the array then u merge them together in the original one .

i'm still having out of range error so im still looking what i did wrong