Thread: C++ MergeSort

  1. #1
    Registered User
    Join Date
    Aug 2009
    Posts
    36

    C++ MergeSort

    I need to learn how to program a Mergesort and I want to actually LEARN IT, not copy and paste some code from google for an easy A. Does anyone know a good place to get a tutorial on this? The one on this site is too short and doesn't actually help you code it at all and I'm a hands on learner.

    I know the basic concept is to keep dividing the list until you get two sorted lists and then put them back together left to right like

    ii = 0
    if(left < right)
    left = array[ii]
    ii++;

    SOmething like that. Any help would be nice

  2. #2
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,739
    Here it is. You know, google and its results can offer you more than just copy-paste code...
    Devoted my life to programming...

  3. #3
    Registered User
    Join Date
    Aug 2009
    Posts
    36
    Yeah I've googled it a bunch but it just seems to stress me out when I pay for this college class to learn hwo to code, which I have learned a lot but then on the final he wants us to learn it ourselves but its his job to teach us. Idk, just doesn't add up to me. Thank you for finding the link for me!

  4. #4
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,739
    Well, actually, your college professor is worth paying for. Finding out new information, called "Data Mining", is an essential capability of a programmer.
    Devoted my life to programming...

  5. #5
    Registered User
    Join Date
    Aug 2009
    Posts
    36
    I hope so. This is very hard for me. Feel like my head is going to explode =). I really do feel a huge sense of accomplishment whenever I successfully program something.

  6. #6
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    As long as you get the basic understanding of the algorithm, you can learn a lot by studying existing examples of said algorithm.
    When you think you have it all down, start writing your own. These algorithms can be tricky to debug, so you might want to compare to already written ones and see where they differ from yours.
    And don't worry--there are usually much better sources than Wikipedia to help you understand and implement such algorithms.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  7. #7
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Back when I learned how sorting algorithms work, it helped me a lot to take a deck of cards, arrange some cards (say, twenty) in random order on the table, and then apply the algorithm by hand.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  8. #8
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Visual graph never hurts, either. I used to look at some of those while sorting data and trying to match my data input to that of the graph and see how it progress and compared it to my own output step by step.
    There are some sites that provides a step-by-step guide through sorting algorithms.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  9. #9
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Not sure what is hard to understand about merge sort.

    Assume you have two lists of things, both of which are sorted. How would you... "merge..." these two lists into a single list, which is still sorted? That's all there is to it.

    How do you get the two lists sorted in the first place? You merge sort them.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  10. #10
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    The problem, I gather, is not logic, but rather implementing and getting it right.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  11. #11
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Quote Originally Posted by Elysia View Post
    The problem, I gather, is not logic, but rather implementing and getting it right.
    Not to argue, but I've had a terrible history with merge sort and if you don't know how to merge then logic and correct implementation are basically the same problem. It was very hard, for me personally, to get merge sort even if I watched it happen.

  12. #12
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Hey, I was trying this myself and ran into some problems.
    If the type is std::list<int>
    Would it be possible to get an iterator to the middle of the list without first running a loop and getting to the middle by evaluating size()/2?

  13. #13
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    If the type is list<int> you should be using list<int>::sort(), but no. List iterators work in forward or reverse order, and for what you want to do to work, you need random access iterators, which list does not provide (with good reason).

  14. #14
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by manasij7479 View Post
    Hey, I was trying this myself and ran into some problems.
    If the type is std::list<int>
    Would it be possible to get an iterator to the middle of the list without first running a loop and getting to the middle by evaluating size()/2?
    This is an impossibility since it's a linked list. The only way to get to the middle is to follow the links one-by-one.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  15. #15
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Actually even evaluating size()/2 might require a walking of the entire list on some compilers, notably gcc.
    Other options are to split the list in two by throwing each even and odd item into separate lists, essentially unzipping the elements. Unfortunately this tends to be slightly slower though because sorted data then throws branch prediction to hell during the actual merge (or whatever else the reason might be).
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. my mergeSort
    By Soulzityr in forum C Programming
    Replies: 41
    Last Post: 03-29-2010, 12:27 PM
  2. Mergesort in C
    By Oduig in forum C Programming
    Replies: 2
    Last Post: 09-14-2008, 11:30 AM
  3. Mergesort
    By swanley007 in forum C++ Programming
    Replies: 6
    Last Post: 10-26-2005, 11:45 PM
  4. Mergesort
    By RazielX in forum C Programming
    Replies: 2
    Last Post: 05-04-2004, 06:27 PM
  5. mergesort
    By AmazingRando in forum C++ Programming
    Replies: 14
    Last Post: 02-29-2004, 09:35 AM