Mergesort - Recusive to Iterative?

[Moonlight]

Hi,

I need to convert a "Mergesort" recursive procedure to an iterative "Mergesort" procedure.

The program I am using does not support recursivity and I need to do a Mergesort.

Here is the Mergesort procedure I need to have converted :


protected void mergeSort(int[] A, int begin, int end) {
if(begin != end)
{
int mid;

mid = Math.floor((begin + end) / 2);
mergeSort(A, begin, mid);
mergeSort(A, mid + 1, end);
merge(A, begin, mid, end);
}
}


merge is already iterative, so the problem is to convert mergeSort into iterative (without calls to itself).

I don't know where to ask so hopefully someone will know the answer.

Thanks.

Moonlight

[sheila]

If you are going to do iterative, Bubble sort has one of the worst performances. Insertion sort would be better.

Still, Bubble, Insertion, and Selection are all quadratic sorts. Whereas QuickSort and MergeSort are (I believe? without checking my references) order of nlog(n). This really only matters if you will be sorting really large lists. If you will be sorting really large lists, then you probably don't want to use a Quadratic sort, as you will notice the performance degrade as the list gets longer.

If it is Javascript, then I would think that you are not sorting such a long list, and a quadratic sort would be fine. I would use Insertion sort or selection sort, in that case.

[sheila]

OK, as a result of this thread, I started checking over the links on my SearchandSortAlgos page (make sure there weren't any dead ones), and also watching some of the Java animation comparisons of the various sorts over again. (I've gotta teach this in another month or two, so this is good review for me...)

Anyhow, I knew one of those pages had a non-recursive MergeSort.

Here it is:
http://www.cs.niu.edu/~mcmahon/CS440/sorts.html

Scroll down a bit, and there is code for non-recursive MergeSort. The code is written in C.

<edit...I take it back. The code is in C++>
[This message has been edited by sheila (edited 02-18-01@1:54 pm)]

[Moonlight]

Thanks for the help and the example of the iterative function.

I tried the function and it doesn't seem to work.

It does the following sort order (for a length of 7) :
Original = 1, 3, 6, 2, 4, 5, 7, 0
[0-1]
[2-3]
[4-5]
[0-2]
[4-6]
[0-6]
Ends With = 1, 0, 6, 2, 4, 0, 7,

The second 0 comes before it does [0-2]

The original recursive method gives :
[0-1]
[2-3]
[0-3] <--- The above gives [0-2] but it should been 0-3.
[4-5]
[4-6]
[0-6]

Maybe it's an error on my part...

Moonlight

[sheila]

I completely do not understand what you're saying here.

Also, I can't guarantee that the code I pointed you to is bug-free.

Last year, when I was teaching sorts, I nabbed some code for an example off the web, and (without testing it! what an idiot) used it for an example in class. Ackh! It had bugs in it.

I ended up writing my own QuickSort last year, so that I would understand the code, and know that it worked. That was no trivial task, either.

[sheila]

Oh, iterative Mergesort is truly hideous.

I have a page of links about searching and sorting that I put together last year for my students:
http://www.thinkspot.net/materdei/apcompsci/SearchandSortAlgos/

Maybe one of those links will take you to what you need?

[sheila]

What program are you using that doesn't support recursion? That code looks like it could be c++ to me??

[sheila]

You know, I look at your MergeSort code above (with the calls to itself, the &quot;recursive&quot; version),

and there is really no way to &quot;convert&quot; it to iterative. You really need to learn and understand the whole mergesort algorithm yourself, first, and then write you own code to do it in an interative method. Why don't you pick a different sort, or a different language? This seems like a poor solution to whatever problem ails you?

If you just want to understand how MergeSort works, I'm sure some of the links on my SearchandSortAlgos page (link above) will help you.

[Justin]

For large lists, I prefer a QuickSort method (divide-and-conquer). For smaller stuff, and especially for an almost-sorted list (for example, adding an entry to a sorted list and moving it to it's proper place), I use a bubble sort routine.

Now that I've glanced at the code in question, it's pretty similar to QuickSort, and should be pretty optimal for large lists. I'm guessing this is JavaScript from the looks of it.

The question is, why do you want it to be iterative? If you're going iterative, go with bubble sort rather than Mergesort... but I'm willing to bet that the Mergesort would be a lot faster, since it looks remarkably similar to QuickSort and uses the divide-and-conquer method (which lets you sort with the absolute least possible number of comparisons).

------------------
Justin Nelson
SFE Software (http://www.sfesoftware.com)