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

Here it is. You know, google and its results can offer you more than just copy-paste code...

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!

Well, actually, your college professor is worth paying for. Finding out new information, called "Data Mining", is an essential capability of a programmer.

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.

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.

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.

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.

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.

The problem, I gather, is not logic, but rather implementing and getting it right.

Quote:

---

Originally Posted by Elysia

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.

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?

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).

Quote:

---

Originally Posted by manasij7479

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.

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).