programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Non-recursive mergesort algorithm.

Bob Ivanovich
Ranch Hand
Posts: 34
I am having some trouble understanding the non-recursive mergesort algorithm. I was able to do the recursive version were I keep diving an array into two until I have a length of one or two for all parts and then I would sort & merge as I would go up the stack tree. However for the non-recursive version I am confused as to how it is possible to do this with nested loops. Would you would have to simulate some form of stack memory with code? If so how? Also I found the code for this algorithm so if any one of you could explain the logic to me it would be great!

Code:

Winston Gutkowski
Bartender
Posts: 10575
66
Bob Ivanovich wrote:However for the non-recursive version I am confused as to how it is possible to do this with nested loops. Would you would have to simulate some form of stack memory with code? If so how?

It depends; but one possibility is to maintain each significant value as a List - or indeed, a Stack. Alternatively, you could create an object containing all the values that need to be maintained, and keep a Stack of those.

The fact is that ANY recursive algorithm can be re-written as a linear one; it just involves more maintenance.

Winston

Matthew Brown
Bartender
Posts: 4568
9
Hi Bob. Welcome to the Ranch!

There are two forms of the standard merge-sort algorithm. Top-down, and bottom-up.

The recursive one is top-down: split the array in half, sort each half separately, and merge them back together. As Winston says, although that's naturally recursive you can implement it in a non-recursive way, and yes, one way to do that would be to use some sort of stack data structure.

But when you say the "non-recursive version", I suspect you mean a bottom-up merge sort. That works like this:
- Loop through the array, "merging" adjacent pairs of values (which in this simple case means swapping them if they are in the wrong order, and leaving them alone if they aren't).
- Now loop through again, but this time one step higher, so you're merging adjacent (and already sorted) blocks of length 2.
- Then loop again, merging adjacent (and already sorted) blocks of length 4.
- ...
- Keep going until you only have one block left, which is the sorted array.

Hopefully you can see that's really two nested loops. Each line is a loop, and the whole algorithm is a loop.

You might also find this page useful: http://algs4.cs.princeton.edu/22mergesort/. As well as explaining the algorithms, it has a table for each type showing how it changes the order of swapping.

Campbell Ritchie
Marshal
Posts: 56553
172
I have closed this thread because I thought it was about the same question. Please have a look at that link.

Matthew Brown
Bartender
Posts: 4568
9
OK, about your query on the other thread (which refers to the loop within the mergeWithoutCopy method.

What this is doing is taking two adjacent blocks of an array: from lo to (mid - 1) and from mid to (hi - 1). Then, assuming those blocks are already sorted, it's merging them together so that lo to (hi - 1) of the target array contains all the values sorted.

It does this by setting pointers at the start of each block. It compares the values at those pointers. Whichever is smaller, it copies to the output array and moves that pointer by one. It does this until both pointers reach the end of their block - the first two if statements are checking to see whether one has already reached the end so it only needs to copy from the other.

One possible source of confusion is the way it uses the ++ operator to copy the value and increment the pointer at the same time: to[k] = from[j++]. That sort of trick does make for very concise code in cases like this, but if you're not used to it can be a bit unclear.

(By the way - as Campbell pointed out on the other thread, if you're posting code you found somewhere else you really need to reference where it came from).