Erroneous Merge Sort !?

[excelguru]

I attached all functions, but only the file mergesort is really relevant.
The way I see it, the call to the function "merge" in line 16 is in no way recursive. But my professor insists it is.
I mean, the array "left" only holds one value (the element 0 of arraytosort), and the algorithm thus only sorts
the first and last elements of an array.

Check it out, it's a gorgeous algorithm, easy to understand.

Thanks a lot guys! (I'm studying business administration, but we have this cs course and I'm relatively new to programming so maybe I'm wrong...I don't have a c# compiler and i can only do the initial program statements in c++. That's why i can't let the pc test it )

[excelguru]

Please, I would really love to get some answers...Thanks!

[DataMiser]

You are using recursive calls to mergesort and mergesort calls merge so in effect I suppose it could be said merge is being recursed as well.

[excelguru]

You are using recursive calls to mergesort and mergesort calls merge so in effect I suppose it could be said merge is being recursed as well.

Mergesort is called recursively, but the variable "left" just receives the "leftmost" value, i.e. element 0 of arraytosort, doesn't it?
Then the program moves on and merge is called with only one element, I guess.
Shouldn't it be something like merge(mergesort(left), mergesort(right)) ?
Thanks a lot for taking the time...what do you think?

[DataMiser]

Well.. it appears that left is an array and will contain at the start the first 1/2 of the array where right contains the second half of the array. With each recursion the array is split into half again and again. After it gets to 1 of the left of the array then it begins the right of the array but if I understand it correctly will begin at the point where right contains only 1 item and then steps back the the recursed tree to the begining calling merge a bunch of times along the way.

Just looking at the code I can't say what the end result would be but those functions would be called several times if the array has many elements in it to start.

[DataMiser]

Looking at the images more closely what I do not see is anything that resembles a sort. It looks like the code is just splitting apart the array and putting it back together.

[DataMiser]

Think about the way your function is going to be called. Lets say there are 4 elements in your array to start. The first time through the array is split into right and left each having 2 elements. Mergesort is called on the left portion and then splits this into right and left 1 element each. Mergesort is called again of the left array which now behaves differently as there is only 1 element.

Mergesort right is called also with only one element now and then merge is called. Result is returned so now we step back one level and mergesort is called again on right this time with 2 elements which causes it split into right and left and call mergesort left again then mergesort right again then merge again and returns a result, once it has stepped through all the recursions of right and lefts then merge is called one more time and result is returned.

What seems to be missing is there is no code that test the value of the data in any element so is any sorting really being done?

[excelguru]

Think about the way your function is going to be called. Lets say there are 4 elements in your array to start. The first time through the array is split into right and left each having 2 elements. Mergesort is called on the left portion and then splits this into right and left 1 element each. Mergesort is called again of the left array which now behaves differently as there is only 1 element.

Mergesort right is called also with only one element now and then merge is called. Result is returned so now we step back one level and mergesort is called again on right this time with 2 elements which causes it split into right and left and call mergesort left again then mergesort right again then merge again and returns a result, once it has stepped through all the recursions of right and lefts then merge is called one more time and result is returned.

What seems to be missing is there is no code that test the value of the data in any element so is any sorting really being done?

"Result is returned so now we step back one level and mergesort is called again on right this time with 2 elements "
That's what I don't get right now. After the function merge returns result the program flows on and returns the final value (result). Stop. Why does it step back?

If you check out the picture merge and merge2, I think you will see that sorting is being done there. Check it out. These pictures are the function merge, which is being called from within mergesort.

[DataMiser]

Let's see when the program calls mergesort and the mergesort calls mergesort again and again. Result is returned to the routine that called that instance of mergesort which then continues to the next line and eventually returns result to the routine that called this instance and continues until we get back to the original call which should get the combination of all the results as a result.

[DataMiser]

---> MergeSort --> MergeSort --> Mergesort
<--Result <---Result <-- Result

Remember mergesort calls mergesort twice and also calls merge so there is more to do after result is returned

[excelguru]

---> MergeSort --> MergeSort --> Mergesort
<--Result <---Result <-- Result

Remember mergesort calls mergesort twice and also calls merge so there is more to do after result is returned

I see, so result is returned to mergesort in line 17 and then to the variable which originally called mergesort (in this case left and right) ?

I previously thought that the whole program stopped after it ran thru line 17 for the first time, because left and right had already received the results from their calls when the length was 1 in line 8 (return arraytosort)
But apparently the call by left to mergesort is not finished yet,right?

Thanks you are helping me a great deal...we don't actually have to understand the details of the program for the exam (it's a business school) but I'm really interested in understanding this thing.

[DataMiser]

If we have 4 elements initially when mergesort is called then we will see something like this at time of execution.

Left=MergeSort .... passing 2 elements so mergesort will call itself again
    Left=MergeSort .....  passing 1 element so we should get a result here
    Right=Mergesort ... passing 1 element so we get a result here
    Merge
    Return Result
Right=MergeSort ... Passing 2 elements so will call itself again
    Left=mergesort ... passing 1 element 
    Right=Mergesort ... passing 1 element
    Merge
    Return result
Merge
return result

Of course it there were more items that process would go deeper, possibly much deeper

[excelguru]

Now it rang a bell!

I guess, recursion can get a lot more intriguing than in the basic factorial and similar beginners' algorithms...

One last thing, when do you know that a recursive call has ended and that the program can finally flow on?
I mean, why does the recursive call left = mergesort(left) end exactly after the first return in line 18?
Does the function maybe have been completely ran thru once?