Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.

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

share|improve this question
add comment

3 Answers

up vote 2 down vote accepted

I found a nice c# sorting implementation at link text

share|improve this answer
add comment

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?)

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.
{"cc_re__cc_re__cc_by_sa_3_0": ["        <li><a href=\"http://area51.stackexchange.com\" title=\"proposing new sites in the Stack Exchange network\">Area 51</a></li>\r\n                        <li><a href=\"http://careers.stackoverflow.com\">Stack Overflow Careers</a></li>\r\n                    \r\n                </ol>\r\n            </td>\r\n    </tr>\r\n</table>\r\n                </div>\r\n            </div>\r\n\r\n            <div id=\"copyright\">\r\n                site design / logo &#169; 2014 stack exchange inc; user contributions licensed under <a href=\"http://creativecommons.org/licenses/by-sa/3.0/\" rel=\"license\">cc by-sa 3.0</a> \r\n                with <a href=\"http://blog.stackoverflow.com/2009/06/attribution-required/\" rel=\"license\">attribution required</a>\r\n            </div>\r\n            <div id=\"svnrev\">\r\n                rev 2014.7.11.1706\r\n            </div>\r\n            \r\n        </div>\r\n    </div>\r\n    <noscript>\r\n        <div id=\"noscript-warning\">Stack Overflow works best with JavaScript enabled<img src=\"http://pixel.quantserve.com/pixel/p-c1rF4kxgLUzNc.gif\" alt=\"\" class=\"dno\"></div>\r\n    </nos"], "copyright__copyright__copyright": ["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;-).\n\nshare|improve this answer\nadd comment\n\nYour Answer\n\n\u00a0\ndiscard\n\nBy posting your answer, you agree to the privacy policy and terms of service.\n\nNot the answer you're looking for? Browse other questions tagged or ask your own question."]}