Thread: 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.

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.

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?