Natural Mergesort

This is a discussion on Natural Mergesort within the C Programming forums, part of the General Programming Boards category; Hi, I have to code bottom-up mergesort and natural mergesort (array). I've got the previous one already. I need help ...

  1. #1
    Registered User
    Join Date
    Sep 2006
    Posts
    51

    Unhappy 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

  2. #2
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    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.

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    51
    but if i split it recursively in the middle, i wouldn't be taking advantage of the "naturally" present ascending order in the subarray.

  4. #4
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    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

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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

  6. #6
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    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.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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.
    Last edited by iMalc; 04-08-2007 at 04:18 PM.

  8. #8
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    Quote Originally Posted by iMalc View Post
    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.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by KONI View Post
    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.
    Last edited by iMalc; 04-08-2007 at 05:30 PM.

  10. #10
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,047
    > what prelude writes himself
    Erhm . . . herself?
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  11. #11
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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

  12. #12
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    Quote Originally Posted by iMalc View Post
    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

  13. #13
    Registered User
    Join Date
    Sep 2006
    Posts
    51
    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

  14. #14
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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

  15. #15
    Registered User
    Join Date
    Sep 2006
    Posts
    51

    Lightbulb

    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?

Page 1 of 3 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Mergesort in C
    By Oduig in forum C Programming
    Replies: 2
    Last Post: 09-14-2008, 11:30 AM
  2. How do I do MergeSort versus QuickSort instead?
    By dxfist in forum C++ Programming
    Replies: 9
    Last Post: 03-06-2008, 11:12 AM
  3. Mergesort
    By swanley007 in forum C++ Programming
    Replies: 6
    Last Post: 10-26-2005, 11:45 PM
  4. Linked Lists + MergeSort....(how?)
    By JoshR in forum C++ Programming
    Replies: 4
    Last Post: 06-03-2005, 02:40 PM
  5. natural leg movement
    By DavidP in forum Game Programming
    Replies: 32
    Last Post: 01-11-2004, 08:01 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21