vector merge sort

[kornunknown13]

template <class T>
void sort(T s, T e)
{
	unsigned int m = (s + e)/2;
	if(m - s >= 2)
	{
		sort(s, m);
	}
	if(e - m >= 2 )
	{
		sort( m+1, e );
	}
	merge( s, m, e );
	
}

template <class T>
void merge_sort( Vector<T> & v )
{
	unsigned int start = 0;
	unsigned int end = v.size() - 1;
	sort (start, end);	
}









int main(int argc, char ** argv)
{
	VECTOR v1;
	v1.push_back(4);
	v1.push_back(10);
	v1.push_back(1);
	v1.push_back(23);
	v1.push_back(20);
	v1.push_back(15);
	v1.push_back(13);
	v1.push_back(5);
	merge_sort(v1);
	 for ( unsigned int i = 0; i < v1.size(); i++ )
	      std::cout << v1[i] << " ";
	std::cout << std::endl;
	std::cout << "All tests passed.";
	std::cin.get();

}

So I have this code where on the top of all this i put int * v = new int[0]; to attempt to make my pointer to my array global
I have been trying to figure out what it is doing step by step. When merge_sort is called the vector in main is still there but once sort() is called my vector from main turns into absolute gibberish and i dont understand why. How can i get my vector from main to stay intact throughout the merge_sort process im feebly trying to create?

[TheDestroyer]

You're passing NO VECTOR to your sort function... you're just passing some indices...!!! it's like if I tell you sort the money bills in my wallet, and tell you that you can start from bill 0 to bill size() -1... would you be able to sort it? I definitely have to give you my wallet too!!!

So!
1- I don't understand why you have to have 2 functions for that
2- I don't know why you need to globalise any pointer...
3- I dont get it why you keep calling the function "sort" recursively!!!! it's like me telling you "sort... sort... sort... sort... sort..." for ever!!! will that make you sort my stuff? ^^ I think your program is just going into an infinite loop by just recalling the same "useless" function again and again...!

As a basic fix for your code (not total), I'd suggest the following:

template <class T>
void merge_sort( Vector<T> & v )
{
	unsigned int s = 0;
	unsigned int e= v.size() - 1;
        for(long i = 0...) //some loop
        {
              for(long j = i...)
              {
                  if(v[i] > v[j])
                  {
                       //switch between elements
                  }
              }
        }
}

int main(int argc, char ** argv)
{
	VECTOR v1;
	v1.push_back(4);
	v1.push_back(10);
	v1.push_back(1);
	v1.push_back(23);
	v1.push_back(20);
	v1.push_back(15);
	v1.push_back(13);
	v1.push_back(5);
	merge_sort(v1);
	 for ( unsigned int i = 0; i < v1.size(); i++ )
	      std::cout << v1[i] << " ";
	std::cout << std::endl;
	std::cout << "All tests passed.";
	std::cin.get();

}

That last code is a basic sorting algorithm... You don't need more than 1 function for sorting. When you write too many functions you just confuse yourself more!!!

Good luck!

[kornunknown13]

well my goal is to learn how to use and understand mergesort correctly and in the pseudo code i have seen they have one function that recursively breaks up the elements into smaller bits and another function that merges them together until the entire array is sorted. And i assumed if i had a global pointer to an array that it could be used through both functions with no problem but i guess not. haha

[TheDestroyer]

I have implemented merge sort once. The simplest way to do it, is to have a buffer vector in each go, and sort every 2^n elements together (2, 4, 8, ...), and place them in the buffer vector. After each go, copy the result in your original vector. So a part of the elements will be sorted. And eventually the whole original vector.

And you don't really have to "cut" your original vector. Just run a few loops inside it and choose the upper and lower limits in a way that makes it act like a real "cropping" from the merge sort algorithm.

One more note about this, make sure that you get stable results at the end; which means, if some elements are equal, the sorting should not flip their order. It's one of the advantages of merge sort.

Good luck!

[kornunknown13]

Thanks for the suggestion!