Thread: sorting a linked list using merge sort question..

  1. #1
    Banned
    Join Date
    Aug 2009
    Posts
    43

    sorting a linked list using merge sort question..

    i thought of breaking it into two lists merge them and sorting them
    in this way
    Code:
    node* merge(node* l1,node* l2)
    {
        if ((!l1)&&(!l2))
        {
             return NULL;
        }
        if (!l1)
        {
            v1=99999999999;
            v2=l2->val;
         }
         if (!l2)
        {
            v2=99999999999;
            v1=l1->val;
         }
        if (v1>v2)
        {    
        l2->next=merge(l1,l2->next); 
        return l2;
        }
        else
        {
           l1->next=merge(l1->next,l2); 
           return l1;
         }
    }
    but i dont have this breaking into two stuff here??

    because i need to sort a single linked list
    ??

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Use selection sort instead, you'll be 100% happier, guaranteed. Merge sort is fine, but stinks on a linked list.

  3. #3
    Banned
    Join Date
    Aug 2009
    Posts
    43
    Quote Originally Posted by Adak View Post
    Use selection sort instead, you'll be 100% happier, guaranteed. Merge sort is fine, but stinks on a linked list.
    i'll do both.
    first my original question:
    i got an idea to use a spliting function
    i split it in half and send it to merge.
    Code:
        node* split(node* l)
       {
             node* l1,*l2,*t,*r;
            l=t=r;
            if (!l) return NULL;
            if(!l->next) return l;
           while(r)//turtle rabbit algorithm
           {
              r=r->next;
              prev=t;
              t=t->next;
              if (t->next)
              {
                     r=r->next;
               }
             prev->next=NULL;
             return merge(l,t);
        }
    its not a real mergesort because i split it only ones
    ??(is it ok??)

    regarding sorting by selection sort :
    i only can sort it by value.(fliiping the values)
    there is no way i could think of so many relinking to do
    in a recursive way.(like i did before)
    Last edited by kakaroto; 08-07-2009 at 03:17 AM.

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Is it OK to split a mergesort just once? No. Mergesort relies on each sub-string being sorted before the two are merged together. It could happen with just a single split, but it's *extremely* unlikely.

    You don't have to re-link all the nodes as you sort, just swap the values which the nodes contain. That's fine! You can swap a whole struct very easily, with all it's members, if you need to. You don't have to swap each member of the struct, individually.

    An alternative would be to use mergesort on the larger substrings, and use selection sort, on only the smaller substrings, after you've made a split or two (or four or whatever), and then merge the substrings back together again.

    Do you *have* to use a mergesort as one of your linked list sorting algorithms?

  5. #5
    Banned
    Join Date
    Aug 2009
    Posts
    43
    but look at my merge function
    it doesnt need a sorted lists
    its merging two unsorted lists
    into a sorted one

  6. #6
    Banned
    Join Date
    Aug 2009
    Posts
    43
    ahh you are correct

    Code:
     node* split(node* l)
       {
             node* l1,*l2,*t,*r;
            l=t=r;
            if (!l) return NULL;
            if(!l->next) return l;
           while(r)//turtle rabbit algorithm
           {
              r=r->next;
              prev=t;
              t=t->next;
              if (t->next)
              {
                     r=r->next;
               }
             prev->next=NULL;
             return merge(split(l),split(t));
        }

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by kakaroto View Post
    but look at my merge function
    it doesnt need a sorted lists
    its merging two unsorted lists
    into a sorted one
    I've heard of the turtle & rabbit algorithm, but have not used it or studied it. I don't have any opinion of it, pro or con, nor do I know if you have implemented it properly.

    There are more ways to sort data than you might imagine. If you want a recommendation for sorting a linked list, I recommend selection sort. If you have another algorithm that works, and you like it's performance, then sure, use it.

  8. #8
    Banned
    Join Date
    Aug 2009
    Posts
    43
    ok thanks
    Last edited by kakaroto; 08-07-2009 at 04:50 AM.

  9. #9
    DESTINY BEN10's Avatar
    Join Date
    Jul 2008
    Location
    in front of my computer
    Posts
    804
    Ok. I have a question, which is related to sorting a linked list, and that's why I didn't create any thread for it. I just want to sort a singly linked list, should I also go for selection sort(I'm assuming heap sort), as Adak posted in his earlier post in this thread. I want the code to be most efficient.
    HOPE YOU UNDERSTAND.......

    By associating with wise people you will become wise yourself
    It's fine to celebrate success but it is more important to heed the lessons of failure
    We've got to put a lot of money into changing behavior


    PC specifications- 512MB RAM, Windows XP sp3, 2.79 GHz pentium D.
    IDE- Microsoft Visual Studio 2008 Express Edition

  10. #10
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Insertion, bubble, and selection sort are all very fast if the number of items to be sorted is less than 25 or so. Even in arrays, they're quicker than standard Quicksort (and frequently used as an enhancement to Quicksort, on the smaller sub arrays it generates).

    After 25, I would look at Cocktail and Comb 11 algorithms, because they're basically bi-directional versions of one (sometimes two), of the above sorting algorithms. I've only tested the Comb 11 version on arrays, but it is *very* good on large quantities of data - within a hair of equaling Quicksort. I'm not a big fan of Heapsort, but it can also be quite fast.

    You will need to do some testing on linked list sorting, to see what works best with your specific data.

  11. #11
    DESTINY BEN10's Avatar
    Join Date
    Jul 2008
    Location
    in front of my computer
    Posts
    804
    Quote Originally Posted by Adak View Post
    You will need to do some testing on linked list sorting, to see what works best with your specific data.
    How? I mean by calculating the Big O thing or something else.
    HOPE YOU UNDERSTAND.......

    By associating with wise people you will become wise yourself
    It's fine to celebrate success but it is more important to heed the lessons of failure
    We've got to put a lot of money into changing behavior


    PC specifications- 512MB RAM, Windows XP sp3, 2.79 GHz pentium D.
    IDE- Microsoft Visual Studio 2008 Express Edition

  12. #12
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Adak View Post
    Use selection sort instead, you'll be 100% happier, guaranteed. Merge sort is fine, but stinks on a linked list.
    This is completely false. I've done comparative performance testing with sorts on a linked list (bubble, insertion, selection, merge and quick), and merge sort has all the advantages over selection sort, etc that it does on an array. Which is to say, on a very large linked list, it and quicksort perform exponentially better than anything else, including selection sort. That is, they will do in seconds what takes minutes for selection sort.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    Quote Originally Posted by MK27
    Which is to say, on a very large linked list, it and quicksort perform exponentially better than anything else, including selection sort.
    Agreed, plus merge sort on a linked list does not need the extra space consumption as does merge sort on an array.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  14. #14
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by laserlight View Post
    Agreed, plus merge sort on a linked list does not need the extra space consumption as does merge sort on an array.
    Yep, because you just swap pointers. I just tried this again to demonstrate:

    Command (h for help, Q to quit): N
    How many records? 25000
    New list is 3515.62 kb

    Command (h for help, Q to quit): s

    Selectionsorting....
    624950002 Iterations Comparison calls: 312487500
    Elapsed time: 2 min 10 sec


    Command (h for help, Q to quit): S
    Shuffled.

    Command (h for help, Q to quit): m

    Mergesorting..............24999 function calls
    503757 Iterations Comparison calls: 334111
    Elapsed time: 0 min 0 sec


    The bigger the list, the more severe the difference. Merge sort will still do 100's of thousands in several seconds, while selection sort is simply not worth waiting for at that point.

    If anyone wants to look at the implementation I used for that:
    linklist_comparative-sorts.c
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  15. #15
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by BEN10 View Post
    How? I mean by calculating the Big O thing or something else.
    Big O notation is a good overall guide, but it's not based on actual run-time. If you want good results for your program, with your target computer, and your typical data, then that's what you should test with, and use actual run-time as your guide.

    I will add mergesort to my list of good sorters for large sized linked lists. Thanks for that correction.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with linked list sorting function
    By Jaggid1x in forum C Programming
    Replies: 6
    Last Post: 06-02-2009, 02:14 AM
  2. Linked list question
    By caduardo21 in forum C Programming
    Replies: 2
    Last Post: 01-30-2005, 01:29 AM
  3. linked list stack question
    By Drew in forum C++ Programming
    Replies: 2
    Last Post: 09-11-2003, 05:05 AM
  4. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 09:27 PM
  5. Quick question on sorting a singly linked list
    By Ham in forum C++ Programming
    Replies: 1
    Last Post: 10-08-2001, 11:26 PM