Notices
Results 1 to 6 of 6

Thread: Merge Sort

  1. #1 Merge Sort 
    New Member
    Join Date
    Jan 2007
    Posts
    1
    Wikipedia states that merge sort is often the best choice for sorting a linked list.

    I don't understand what this statement means.
    Aren't all sort algorithms for sorting a list of something?
    If someone can explain what this means, I would appreciate.


    Reply With Quote  
     

  2.  
     

  3. #2  
    Guest
    If you provide a link to the wiki page, or indicated if you are talking a specific language, or said you were using a particular software package... Get the idea? 8)


    Reply With Quote  
     

  4. #3  
    New Member
    Join Date
    Jan 2007
    Location
    Kings Park
    Posts
    4
    I am not exactly sure why they say it is better used in a linked list.

    However, I can tell you why they say it is stable.

    MergeSort always does the same number of comparisons. If you used QuickSort (if list is in right condition, quicksort is much faster than that of MergeSort) on a list that was exactly the opposite of the order it was sorting at (if the list went from greatest to smallest while you wanted to sort smallest to largest) the time it takes is O(n2). Using MergeSort and using a function that allows it to find the best middle position (int middle = (left - (right-left))/2) is a great choice and thus stabilizes the code even further.

    Again, i am not sure why they say using it on a linked list is beneficial. In most cases, you dont want to change the data your sorting. The only way I see mergeSort better than QuickSort is if you do change your data linked list to store an additional field (such as Position (head, tail, middle, etc.)).

    Anways, I am a fan of HeapSort.
    If you can't explain it simply, you don't understand it well enough.

    - A. Einstein
    Reply With Quote  
     

  5. #4  
    Guest
    Reply With Quote  
     

  6. #5  
    New Member
    Join Date
    Jan 2007
    Posts
    3
    A linked list is a particular implementation of a list.
    A linked lists consist of nodes, each one having an element (the thing you want to sort), and a pointer/reference to the next node in the list (and may be to the previous too)...
    Code:
    struct Node
    {
        int Element;
        Node* Next;
        Node* Previous; //Optionally
    };
    The operations performed by MergeSort are really easy (and efficient) to implement in a linked list. So the constants factors of the function will be probably very small... The operations of quicksort, or other sorting algorithms aren't that easy/efficient to implement on a linked list. Also MergeSort in a linked list doesn't require additional space, quicksort needs O(Log n) and other algorithms may have other disadvantajes...
    Reply With Quote  
     

  7. #6  
    Forum Freshman
    Join Date
    Feb 2007
    Posts
    6
    hi every body
    usually merg sort the the best choice, because if you think in a deeper way you will find that its complixty is minimum, you compare each element in the first portion with maximam all elementns in the other portion. so its complixty is n+m-1(minus one because we dont compar the last element) can you understand any thing from me I hope you did
    Reply With Quote  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •