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.

2.

3. 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)

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.

5.

6. 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...

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

 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   BB code is On Smilies are On [IMG] code is On [VIDEO] code is On HTML code is Off Trackbacks are Off Pingbacks are Off Refbacks are On Terms of Use Agreement