Help with merging dynamic stacks

[rubito]

I'm working on an assignment that asks us to write a mergesort program. I have the mergesort function but I'm stuck at the merge function. This is what the assignment asks for the merge function

T* merge(T* left, T* right, int sizeLeft, int sizeRight)

assumes left and right are sorted arrays
all pointers to newly created arrays are placed on the pointers stack
returns a pointer to a sorted combination of left and right

This is what I have for my functions:

  template<typename T>
MergeSort<T>::sort(T arr[], int size)
{
    mergeSort(pointers.push(T*sortedArr[size]));
    {
        //change this to other way
        std::array<size> arr = sortedArr;
    }
}

template<typename T>
MergeSort<T>::~MergeSort()
{
    while(!pointer.empty())
    {
        pointers.top();
        pointers.pop();
    }
}

template<typename T>
T* MergeSort<T>::merge(T*left, T* right, int sizeLeft, int sizeRight)
{
    T*tempArr = new T[left + right];
    //find a way to copy both values to one sorted array
    return tempArr;
}

template<typename T>
T* MergeSort<T>::mergeSort(T*arr, int size)
{
    //T* tempArr = new T[size];
    int sizeLeft = size/2
    int sizeRight = size-(sizeLeft);
    //split the array into two
    T* left = arr;
    T* right = arr + sizeLeft;


    if (size == 1)
    {
        return arr;
    }

    //merge sort the left array
    T* sortedL= mergeSort(left, sizeLeft);
    //merge sort the right array
    T* sortedR= mergeSort(right, sizeRight);
    //merge the sorted left and right array
    return merge(sortedL, sortedR, sizeLeft, sizeRight);
}

My main concern is the merge() class. Thanks for all the help

[AbstractionAnon]

Line 24 should be:

T* tempArr = new T[leftsize + rightsize];

What you want to do at line 25 is to loop comparing elements of left and right. If you've reached the end of both left and right, exit the loop. At each step, compare left to right. If left < right add left to tempArr and increment left index, otherwise, add right to tempArr and increment right index. Don't forget that the left and right can be different sizes. e.g. if you've reached the end of left, but not right, everything remaining in right should be added to tempArr since everything remaining is greater than right. Likewise, if you reach the end of right, you need to add everything remaining in left.

[rubito]

In order to check if I've reached the end could I use getNext()?

[rubito]

Is this what you meant about adding left to tempArr and otherwise?

template<typename T>
T* MergeSort<T>::merge(T*left, T* right, int sizeLeft, int sizeRight)
{
    T*tempArr = new T[sizeLeft + sizeRight];
    //find a way to copy both values to one sorted array
    while (!(sizeRight + sizeLeft)==size)
    {
       if (left < right)
       {
           tempArr = [tempArr + left];
        sizeRight++;
       }
        
        else
            tempArr = [tempArr + right];
            sizeLeft++; 
    }
    return tempArr;
}

[AbstractionAnon]

In order to check if I've reached the end could I use getNext()?

I don't see a getNext() function.

Is this what you meant about adding left to tempArr and otherwise?

Line 6: You're comparing the pointers to the respective arrays, not the elements.

Line 8, 12: You're overwriting the pointer to tempArr which you allocated at line 4. This is a memory leak and will cause your program to crash.

Line 9 and 13: You're changing the size of the respective arrays. Not what you want to do.

Try something like this:

template<typename T>
T* MergeSort<T>::merge(T* left, T* right, int sizeLeft, int sizeRight)
{  T* temp = new T[sizeLeft + sizeRight];
    int il = 0;		// Index to left array
    int ir = 0;		// index to right array
    int ix = 0;		// Index to result array
	
	while (il != sizeLeft && ir != sizeRight)
	{	if (il == sizeLeft)
		{	// Done with left.  Copy right element
			temp[ix++] = right[ir++];
			continue;
		}
		if (ir == sizeRight)
		{	// Done with right.  Copy left element
			temp[ix++] = left[il++];
			continue;
		}
		//  Have elements left on both sides
		if (left[il] < right[ir])
		{	temp[ix++] = left[il++];
			continue;
		}
		//	right must be <=
                                temp[ix++] = right[ir++];
            }       
    return temp;
} 

[rubito]

Ohh I see, so since I'm already passing a sorted array I can just advance in a linear way by using index++. Thanks a lot for the help. I'm a beginner and I'm having a hard time dealing with classes that are so dependent on each other.