Hi,
Can someone recommend me a sorting algorithm for my custom link list + example, basically it is similar to the Generic LinkedList so if you could give examples for the Generic LinkedList it will be great.
I am planning to implement the merge sort, please advice on the pros/cons as I am not so familiar with any algorithm, just taken the idea of merge sort algorithm from google.
c# examples only if possible :)
Cheers
This sounds a lot like homework. Wikipedia has some good pseudo-code for you to start with.
As to which algorithm is the best, it depends on memory constraints, processing power, sample size, data type, and much more. There is no "best" algorithm (Although there are worst algorithms. Bubble sort anyone?)
Mergesort's a good idea, because, differently from other advanced sorts, does not require indexability (so it works fine on linked lists as well as arrays). A general intro in C# is here -- it doesn't use generics, and uselessly introduces arraylists and indexing where things could perfectly well proceed by iteration, but I can't find an elementary intro in C# done right.
A caveat in all advanced sort algorithms is that it's often best, in recursion, to not use the "advanced algo" all the way down, but rather switch to simpler ones for sufficiently smaller sublists -- the simple algorithms have worse big-O, but smaller multiplicative constants, so the mix can often be optimal.
A worthy variant is natural mergesort, which takes advantage of runs that may already be present in the data -- the URL I've given uses pseudocode, but it's pretty readable. Natural mergesort is great for data that are already mostly sorted but with a few items out of order, e.g. appended at the end -- it can offer asymptotic O(N) performance when the few items are indeed few;-).