Merge Sort - 'almost' working

I prefer Sedgwick, _Algorithms in C_. (Parts 1 - 4)

What doesn't it do?

What does it do?

All the sP, eP and mP's make my head hurt, but I don't see where you actually compare the elements and select the larger or smaller one, you seem to just step through the arrays.

Oh, I see now.

But shouldn't this:

short *array = new...

just be short array = new...

You don't want an array of *pointers*

Not in C, but I am not that familiar with Objective C.

Why not just use straight C:

short array[num_elements];

Which is *definitely* an array of shorts.

If it is C++ then why don't you just use the "sort" algorithm?

I used to be a big fan of C++ until it finally dawned on me I was just wasting my time with a truly awful language.

The first thing to do in a situation like this is print out your array before and after. That will give you a much better idea of what is going on. You can still using printf() in C++. There is no reason to torture yourself with iostream. Once you do that, you will see that you are actually overflowing your data. The problem line is this one:

for (short var = sP; var <= eP; ++var) array[var] = tempArr[var];

In this function sP can start at any location in the original array but tempArr always starts at 0. Re-use that temp_iter for tempArr and start it at 0. That will take care of it and transform this:

/tmp $ ./a.out

-74 -49 -68 -86 -28 91 25 -62 -96 -71 -29 26 28 -78 23 -30 -21 -33 -74 39 41

-6868 -30677 -74 -74 -74 -74 0 0 0 0 0 0 2 0 0 0 0 0 91 -6868 256

to this:

/tmp $ ./a.out

6 54 -55 64 -44 80 68 -3 -37 -39 47 -49 -92 -21 92 -79 92 33 2 -33 61

-92 -79 -55 -49 -44 -39 -37 -33 -21 -3 2 6 33 47 54 61 64 68 80 92 92

Sorting algorithms are *extremely* fine tuned. By changing any thing substantive (i.e., putting in something other than a print statement) you are probably changing it into some *other* sorting algorithm, or simply breaking it.

One reason I like Sedgewick is that he has really good summaries of the algorithms and good illustrations of the metrics.

Also, random data is not necessarily the best for sorting. Sedgwick always starts by sorting "ASORTINGEXAMPLE" so you can tell at a glance whether it is working.

BR41N-FCK wrote:

If I had a project with a short deadline - sure, I'd use a pre-made (what else can we call it?) solution. But right now I am learning algorithms, so there's no point using ready ones.

The only reason for the sorting and linked-list exercises is to give students some experience with challenging, but solvable problems in programming. Don't get me wrong, there is great value in that. However, it would be better done in C or even Pascal. Computer Science teaching kind of went off the deep end in 1990 or and has only gotten worse.

Thank you for solving my problem. It was so simple... and maybe that's why I have overlooked it :-)

One of the skills a programmer must have is how to debug such problems. That doesn't always mean running in a debugger. I very rarely use a debugger. Most modern, UI or server work is far too complex for such things. Simple "printf" statements are usually all that is required.

Speaking of C++. Why would you call it awful? I mean it isn't the best for developing windowed apps (see: objective-c and c# on windows), but it is great for console ones and also it is good for education purposes thanks to its plain syntax (compared to c# and not to even mention the crazy syntax of objective-c).

Because I wasted so much of my programming career on it. I suppose it was a valuable lesson. I suspose if someone had told me it was junk in 1995 I probably would have ignored them then. Now I have a decent store of tacit wisdom that is hard to explain. I just "know" when someone does or doesn't know what they are talking about. Just because "everybody is doing it" doesn't mean everybody isn't wrong.

Objective-C syntax is actually quite simple. It is just the message passing through brackets. That is insignificant compared to cryptic C++11. You aren't even using C++ in this program. With the expection of iostream, you are only using C. I don't see any templates, no references, no const-correctness, no virtual functions, no inline code, no iterator traits, no lambdas, no locales, no iomanips. It's all junk that only makes life harder and life is short enough as it is.