Why is my mergesort function only working for arrays up to three items?

[discoverer02]

I'm not sure that this post belongs here, but I'll give it a try. I'm having a devil of a time trying to figure out why my program won't work.

The assignment was to create and array class consisting of:
A constructor that takes and integer for the size of the array
A constructor that takes 2 integers, one for the first index and one for the last index
A copy constructor
Overload []

We were then supposed to pass array objects to a quicksort and mergesort function that came right out of our textbook.

The quicksort function is working just fine with my array class, but the mergesort only works for arrays up to three items. If I try to pass an array object of length 4 or greater the merge function fails.

I've spent hours trying to debug to no avail. The program was created in MS Visual Studio.NET 2003

I'd really appreciate it if a programmer could take a look at it and fill me in on where I went wrong.

Thanks for the help

discoverer02

 

[AKG]

Can you tell us exactly what the problem is? Is your mergesort just not sorting properly, or do you get a runtime error and the program just stops, or do you get strange output?

 

[discoverer02]

Sorry about that. I should have been much more specific.

I pulled the mergeSort and merge functions straight out of the textbook. The only difference is one parameter which is my Array class and the tempArray created in Merge() which is also my Array class.

The mergeSort function is supposed to recursively break the array into smaller and smaller halfs and then the merge function is supposed to put the array back together sorted from lowest to highest. The error is apparently occurring in the merge function.

Everything seems to work just fine for arrays of lengths 0 to 3.

For an array of 4 strings, it completes the merge function once and then apparently crashes there on the second pass.

For the array of 4 strings, the recursive calls go:
MergeSort
MergeSort
Merge
MergeSort
and then it seems to crash in Merge

This is the message that Windows 2000 gives me:

The instruction at "0x0043bf84" referenced memory at "0x000d008b". The memory could not be "written"

 

[AKG]

First of all, did you say you tested your sort for arrays of size 0?

It seems that somewhere your merge sort is trying to access memory outside your array. Look at the places where the function could be trying to write to memory, and see if maybe it's trying to write to the fifth index or something.

Mergesort (0,3)
--> Mergesort (0,1)
-----> Mergesort (0,0) * does not say "entered mergesort" *
-----> Mergesort (1,1) * does not say "entered mergesort" *
-----> Merge (0,0,1,1)
--> Mergesort (2,3)
-----> Mergesort (2,2) * does not say "entered mergesort" *
-----> Mergesort (3,3) * does not say "entered mergesort" *
-----> Merge (2,2,3,3)
--> Merge (0,1,2,3)

I would just have a bunch of cout statements checking what indexes are being worked with, in each while/if block of code to pinpoint where the problem is. I can't see why it would successfully perform the first merge and not the second. Well, the second merge does deal with the end of the array, so perhaps you're going out of bounds there.

I looked at the code, it looks like it should work.

 

[discoverer02]

Thanks AKG.

I figured it out. The book's Merge() function isn't written very efficiently. It requires a tempArray much larger than necessary in order to keep the items in the different arrays in sync during the sorting process. I changed the size of the array from the actual number of items being sorted to the maximum index number being passed to the function.

It works fine now.

Thanks again for your help. It's much appreciated.

discoverer02