Erroneous Merge Sort !?
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 13 of 13

Thread: Erroneous Merge Sort !?

  1. #1
    Join Date
    Jan 2010
    Posts
    9

    Erroneous Merge Sort !?

    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 )
    Attached Images Attached Images     
    Last edited by excelguru; June 3rd, 2010 at 05:17 PM.

  2. #2
    Join Date
    Jan 2010
    Posts
    9

    Re: Erroneous Merge Sort !?

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

  3. #3
    DataMiser is offline Super Moderator Power Poster
    Join Date
    Jul 2008
    Location
    WV
    Posts
    4,786

    Re: Erroneous Merge Sort !?

    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.
    Always use [code][/code] tags when posting code.

  4. #4
    Join Date
    Jan 2010
    Posts
    9

    Re: Erroneous Merge Sort !?

    Quote Originally Posted by DataMiser View Post
    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?

  5. #5
    DataMiser is offline Super Moderator Power Poster
    Join Date
    Jul 2008
    Location
    WV
    Posts
    4,786

    Re: Erroneous Merge Sort !?

    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.
    Always use [code][/code] tags when posting code.

  6. #6
    DataMiser is offline Super Moderator Power Poster
    Join Date
    Jul 2008
    Location
    WV
    Posts
    4,786

    Re: Erroneous Merge Sort !?

    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.
    Always use [code][/code] tags when posting code.

  7. #7
    DataMiser is offline Super Moderator Power Poster
    Join Date
    Jul 2008
    Location
    WV
    Posts
    4,786

    Re: Erroneous Merge Sort !?

    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?
    Always use [code][/code] tags when posting code.

  8. #8
    Join Date
    Jan 2010
    Posts
    9

    Re: Erroneous Merge Sort !?

    Quote Originally Posted by DataMiser View Post
    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.

  9. #9
    DataMiser is offline Super Moderator Power Poster
    Join Date
    Jul 2008
    Location
    WV
    Posts
    4,786

    Re: Erroneous Merge Sort !?

    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.
    Always use [code][/code] tags when posting code.

  10. #10
    DataMiser is offline Super Moderator Power Poster
    Join Date
    Jul 2008
    Location
    WV
    Posts
    4,786

    Re: Erroneous Merge Sort !?

    ---> 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
    Always use [code][/code] tags when posting code.

  11. #11
    Join Date
    Jan 2010
    Posts
    9

    Re: Erroneous Merge Sort !?

    Quote Originally Posted by DataMiser View Post
    ---> 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.

  12. #12
    DataMiser is offline Super Moderator Power Poster
    Join Date
    Jul 2008
    Location
    WV
    Posts
    4,786

    Re: Erroneous Merge Sort !?

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

    Code:
    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
    Always use [code][/code] tags when posting code.

  13. #13
    Join Date
    Jan 2010
    Posts
    9

    Re: Erroneous Merge Sort !?

    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?
    Last edited by excelguru; June 4th, 2010 at 05:31 PM.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center