Natural Mergesort

Hi,

I have to code bottom-up mergesort and natural mergesort (array).
I've got the previous one already.

I need help with natural mergesort.
I've read some lesson/explanations on it, but i don't quite get the splitting part.
I wanna use the same merge func as my BU mergesort if possible.

Let's say i have a list :
2 , 1 , 4 , 5 , 3 , 6 , 1

would the splits be like..
-2 | 3 , 6
-1 , 4 , 5 | 1

and then...
-2
-3 , 6
-1 , 4 , 5
-1

then the merge begins?

My problem is i'm not quite sure of how to implement the runs and splits...would it be a recursion of the sort function?

thx

Seriously, I tried to make sense of what you wrote but I just don't understand it. Just split your initial array recursively in half, cutting at the middle.

but if i split it recursively in the middle, i wouldn't be taking advantage of the "naturally" present ascending order in the subarray.

Natural mergesort is based on merging bitonic sequences (translation from german), which is a sequence of ascending and then descending numbers:

a(i)<=a(i+1)<= ... <=a(i+m)>=a(i+m+1)>= ... >=a(i+k).

The following sequence:
6 8 2 4 1 3 5 7

has the bitonic sequences
6 8 2, 4 1 and 3 5 7

The algorithm does the following:

- first it searches for bitonic sequences in the input array and sort each bitonic sequence into a new array
- the bitonic sequences are sorted alternately ascending then descending, in order to create new bitonic sequences
- once you can't find any more bitonic sequence, your algorithm is done

Your example:

2 , 1 , 4 , 5 , 3 , 6 , 1

split into: 2,1 and 4,5,3 and 6,1
sorted: 1,2 and 5,4,3 and 1,6
put together: 1,2,5,4,3,1,6

again:
split into: 1,2,5,4,3,1 and 6
sorted: 1,1,2,3,4,5 and 6
put together: 1,1,2,3,4,5,6

done

I've never heard of a natural mergesort, but this guy has:
http://penguin.ewu.edu/~trolfe/Natur.../NatMerge.html

About half-way down the page, he also has a link to a C program for it. Looking at his test data, it seems to have good performance. I doubt that, because in a large amount of data, you'd have to go looking through the whole thing to find out if and where there existed a naturally sorted part of that data.

If there's 6 numbers in a row already sorted, in 8 different places, out of a 100,000 numbers, I'd love to see just how natural mergesort would really perform with that.

Adak

As I said, you're not only looking for "already sorted" numbers but for bitonic sequences, which happen a little more frequently. The worst case complexity happens when the numbers are alternately increasing/decreasing, like "1 0 1 0 1 0 1 0" but the general complexity is indeed very good.

KONI, he wants to write natural mergesort, not plain mergesort. As you don't know what this is, you can't help him
He does not want to write bitonic sort, either. Bitonic sort is totally different from natural merge sort.
Best you just stop posting on this particular thread as you're giving too much wrong advice. Harsh, but true.

wuzzo87, are you planning on using two extra arrays of the same size as the original for this? The simplest way to do natural mege sort requires 200&#37; more space than the original array.

Before the loop you copy one item form the original array and put it on the first temp array.
Then you repeat the following until reach the end of the original array:
If the next item in the original array is greater than the last item of the last array you wrote to, write to the same array. If it is smaller than, write it to the other array.
Stop here if you only wrote items to one of the other areays.
Now the merge step:
Scan through both arrays at once and take the smallest item from the current position of each array and copy it back to the original array.
Go back to start.

You don't need any recursion. Simply loop until there is nothing in the second array to merge with the first.

I could point you at Prelude's website, but that might be too much assistance for homework, since you might simply copy the code.

Originally Posted by iMalc

KONI, he wants to write natural mergesort, not plain mergesort. As you don't know what this is, you can't help him
He does not want to write bitonic sort, either. Bitonic sort is totally different from natural merge sort.
Best you just stop posting on this particular thread as you're giving too much wrong advice. Harsh, but true.

Instead of suggesting to other people what they should do or not, I suggest you first read what prelude writes himself:

The algorithms for a natural merge sort can vary wildly, but a simple algorithm that performs well uses two queues to act as each half of the merge.

Afterwards, I want you to learn German and go and read the official website of the University of Flensburg. I am talking of this explanation of the natural mergesort written by professor H.W. Lang, author of the book "Algorithms in Java".

Finally, take your crap advice and keep it for yourself, especially in that harsh tone. I am never giving any advice without first researching and keeping my sources/references.

Originally Posted by KONI

Instead of suggesting to other people what they should do or not, I suggest you first read what prelude writes himself:


Afterwards, I want you to learn German and go and read the official website of the University of Flensburg. I am talking of this explanation of the natural mergesort written by professor H.W. Lang, author of the book "Algorithms in Java".

Finally, take your crap advice and keep it for yourself, especially in that harsh tone. I am never giving any advice without first researching and keeping my sources/references.

I'm sorry I wrote what I did earlier. I should have put a nicer spin on it, and deserved the response I got.

The "simple algorithm" that Prelude speaks of is exactly what I was talking about.

I'm sure you mostly do a good amount of reasearch about stuff before you post it, but such was not exactly the case when you suggested recursively splitting in the middle.

I looked at that page, in fact I had seen it before! Yes it is one way to perform merges, and probably more efficient than what I was referring to. I'm just not sure that a student is expected to implement it in this way. Since the OP made no mention of bitonic merges, I would asume the intent was to use merging of monotoic sequences.

> what prelude writes himself
Erhm . . . herself?

So you're posting crap about KONI's post even though his program's recommendations were BETTER than yours?

"Yes it is one way to perform merges, and probably more efficient than what I was referring to."...

That's a new one!

What's next on your crap list: Da Vinci, Rafael, Monet, Rodin?

Adak

Originally Posted by iMalc

I'm sorry I wrote what I did earlier. I should have put a nicer spin on it, and deserved the response I got.

No problem, nothing anyone could say on the internet actually hurts me, I don't give much about what some anonymous guy on the other end of the world writes about me.

We both only intended to help the op, I didn't know about natural mergesort before and since I was interested, I did some research with google (without checking eternallyconfuzzled first) and stumbled upon that German website. Since I speak German perfectly well, and the source seemed reliable (university website), I explained the algorithm to the op.
It was only later on that I found out that there are actually several possible ways of doing it, one of which you mentioned (I later read up about it on prelude's).
All in all, the op got his answer, we all were able to learn something and we have two possible implementations for the problem

Thank you for ur assistance iMalc, KONI, adak and all.

I'll try coding it by myself for the moment and understanding it.
I'm a bit blurry about the differences between bitonic sort and natural mergesort since you pointed out that natural mergesort also takes advantage of the bitonic order of the elements. But i'll try reading that up myself for the moment.
I'll return if i need a bit more help.

Thx

Natural mergesort may be either monotonic or bitonic. Monotonic implementations take advantage of series of values that scale in one direction only, while bitonic programs take advantage of series of values that scale either upward or downward.

Good question for the forum; you're quite welcome.

Adak

ok, following what iMalc said, this is what i coded so far.....
(I hope i don't sound dumb )

Code:

void mergeN(Record *a, int lo, int hi, int (*comp_func)(const, const))
{
    Record *b = malloc(sizeof(Record)*hi);
    int i=0;
    int k=0;
    int j=i+1;

    /*Copy one item from array to temp*/
    *(a+i) = *(b+i);

    while(i<=hi)
    {
        /*If next item less than what was last
         * wrote to, write to temp*/
        if(comp_func((a+j),(a+i)) < 0)
        {
            *(b+k++) = *(a+j++);
        }
        else
        {
            /*write back to array*/ 
            *(a+i++) = *(a+j++);
        }
    }
}

Not quite sure about that, but it'll give two array with a bitonic order right?

But how do i split it down further?

And, where to merge them?