What is the best algorithm to sort a link list [in C/C++]?
Would you like to elaborate the reason for merge sort. Thanks for suggesting STL, but can't use it because it is homework
Cory W.
2009-11-14 06:27:32
@Cory: of the three common algorithms (heapsort, quicksort, mergesort) it's the only one which performs well without random access
Christoph
2009-11-14 09:57:28
+9
A:
Merge sort is suitable for sorting linked lists. Some details here. Sample C code here.
Why is it suitable? Well, to put it simply, mergesort's main component - the merging of sorted subsequences - can be easily done on two linked lists, because all it ever needs is comparing the head elements, so it doesn't require the random access an array has.
Also, here's an article named A COMPARATIVE STUDY OF LINKED LIST SORTING ALGORITHMS you may find interesting.
Eli Bendersky
2009-11-14 06:39:06
I don't know why people keep linking to this site - the implementation sucks as it is overly complicated and needlessly traverses the list; the algorithm in use is equivalent to the iterative array-based version - which is not suited for linked lists as these don't allow random access - and should be replaced with a stack-based implementation; even the vanilla recursive one should perform better
Christoph
2009-11-14 09:45:30
+1
A:
Depends on what you mean by "best". Do you mean quickest to implement, or most efficient runtime? The size and characteristics of what you're sorting also play a role. Sorting 10 items versus sorting 10 million items will likely lead to a different "best" algorithm. For large datasets where "best" means fastest runtime, I like quicksort.
bpv
2009-11-14 06:45:40
I think I remember hearing that quicksort runs slow on sorted (or nearly sorted) data. So, as bpv said, the characteristics of the data would indeed play a large role in your decision.
veol
2009-11-14 07:26:44
@veol: A naive quicksort runs slow, most practical implementations use randomized pivoting.
MAK
2009-11-14 07:30:55
+1
A:
A stack-based mergesort implementation is the weapon of choice.
Some time ago, I needed to sort a doubly-linked list. Wikipedia told me to use mergesort as it's the only one of the three common general-purpose sorting algorithms (heapsort, mergesort and quicksort) which performs well when random-access is slow and even provided a link to Simon Tatham's implementation.
First, I re-implemented his algorithm, which showed that it was basically the well-known iterative version. It's a bad choice as it relies on random access and therefore performs poorly.
The recursive version is better suited for linked lists as it only needlessly traverses one of the lists when splitting and not both (as does Simon's variant).
What you should use is a stack-based version as this implementation gets entirely rid of unnecessary list traversals.
Christoph
2009-11-14 10:15:12
A:
It's worth thinking about how you got to this point. If you're going to need your items sorted in one particular way, consider keeping the list sorted and inserting them directly into the sorted list. That way you don't have to sort it when you need it.
Tim
2009-11-14 11:49:59