Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I have already studied bubblesort, insertion sort and selection sort and can implement them in C pretty much from knowledge of the algorithm. I want to go on to learn shellsort, merge sort, heapsort and quicksort, which I guess are a lot harder to understand.

What order should I take these other sort algos? I am assuming a simpler sort algo helps learn a more complex one.

Don't mind taking on some others if it helps the learning process.

share|improve this question
1  
I don't think the order really matters. If you prefer, learn the simpler algorithms before the more complicated ones. –  Bernard Aug 15 '12 at 20:50
2  
Learn bogosort before all others ;) –  Demian Brecht Aug 15 '12 at 21:10
2  
Clearly, the order of your sorting algorithms depends on the comparer/predicate you pass into the sorting algorithm you're using. And the original order I suppose if you're using a stable algorithm. Programmers.SE seems like a poor (non-deterministic) sorting algorithm :] –  Telastyn Aug 15 '12 at 21:24
2  
In 15+ years of programming, I've had to sort maybe 3 times. –  dbracey Aug 17 '12 at 6:25
    
It never ceases to amaze me how many different sorts there are. I'd definitely recommend you checking out sleep sort. It's pretty wonderful... I just saw it today and it completely blew my mind. –  alvonellos Sep 8 '12 at 4:14
show 1 more comment

put on hold as off-topic by MichaelT, Bart van Ingen Schenau, World Engineer 22 hours ago

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions seeking career or education advice are off topic on Programmers. They are only meaningful to the asker and do not generate lasting value for the broader programming community. Furthermore, in most cases, any answer is going to be a subjective opinion that may not take into account all the nuances of a (your) particular circumstance." – MichaelT, World Engineer
If this question can be reworded to fit the rules in the help center, please edit the question.

5 Answers

up vote 8 down vote accepted

Learn mergesort and quicksort first: they are both fairly simple, high-performance, and frequently used.

Next, look at heapsort. It is more complicated than mergesort and quicksort, but it is also high-performance and frequently used; also, heapsort is based on a priority queue, which is sometimes a more appropriate solution than sorting an entire array at once.

The above three sorts have O(N log N) asymptotic performance; most practical sorting implementations are based on them.

Shellsort isn't very complicated to implement, but it doesn't really have much to recommend it, either: the algorithms mentioned above perform better, and it is not used much, so I would leave it until later.

For breadth, I would also recommend learning bitonic sort, which aside from being asymptotically slower at O(N (log N)^2) is both complicated and harder to understand -- but it has the advantage of being parallellizable, in ways that many other sorts aren't. If you want to use a GPU to sort things, you should look into bitonic sort.

Finally, radix sort is a bit different: it is not a general comparison sort, which is why it can have an asymptotic speed of O(k N) (for keys of fixed size k). Although IMHO it has sometimes been oversold, radix sort can be made quite fast, and is occasionally used in practice; it is relatively simple, and worth understanding for its own sake.

share|improve this answer
add comment

Most programmers only ever learn these algorithms so that they know that they don't need to implement them. If you're using a well-tested platform such as .NET, Java, Python, etc., it's pretty much insane to write your own sorts. So choose the order that will teach you the most about algorithms, and then make sure you don't ever put it into practice.

share|improve this answer
    
I agree. If your intent is practical, don't bother. But studying sort algorithms is a great way to study programming and algorithms in general. –  ddyer Aug 15 '12 at 21:39
    
Indeed, so if that is one's intention, the order of study should be determined by the learning process rather than the utility of the sorts themselves. –  Dominic Cronin Aug 16 '12 at 6:43
4  
Most programmers only learn and relearn these algorithms every few years when they're interviewing :) –  s d Sep 8 '12 at 2:40
add comment

Coursera's Algorithms, Part 1 covers topics roughly in the following order: union-find, binary search, stacks, queues, bags, insertion sort, selection sort, shellsort, quicksort, 3-way quicksort, mergesort, heapsort, binary heaps, binary search trees, red-black trees, separate chaining and linear probing hash tables, Graham scan, and kd-trees.

Coursera's Algorithms, Part 2 focuses on graph and string-processing algorithms. Topics include depth-first search, breadth-first search, topological sort, Kosaraju-Sharir, Kruskal, Prim, Dijkistra, Bellman-Ford, Ford-Fulkerson, LSD radix sort, MSD radix sort, 3-way radix quicksort, multiway tries, ternary search tries, Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp, regular expression matching, run-length coding, Huffman coding, LZW compression, and the Burrows-Wheeler transform.

share|improve this answer
add comment

Although higher level languages like .NET and Java already come with implemented sort algorithms , it is always better to know the stuff behind the scenes that you are using . These algorithms also teaches some nifty programming techniques that you can apply in your programming .

QuickSort is kind of the most important of these sort algorithms as it achieves a O(n log n) time on average and the constants hiding behind the scenes are pretty good and it sorts in place. Heap Sort too has O(n log n) time in the worst case . Merge Sort also is O(n log n) time in the worst case but it doesn't sort in place . It also gives a good foundation for divide and conquer algorithms . Both randomized QuickSort and HeapSort use divide and Conquer paradigm . Heap Sort uses that indirectly through a procedure called Max-HEapify and quick Sort uses divide and conquer directly . So definitely you should learn MergeSort first and then you can learn Quick Sort and then the Heap Sort . Learning about heap sort also has the added advantage of learning a the heap datastructure .

After these you may want to look at some sort algorithms that achieves O(n) in the worst case like Count Sort , radix sort and bucket sort .

share|improve this answer
add comment

Skip shellsort and heapsort. I'd probably skip merge sort.

You NEED to understand quicksort. Look for an explanation that presents a recursive algorithm first, as it will be much easier to grasp what is going on (pick a pivot element, partition into three sets (elements less than pivot, elements equal to pivot, elements greater than pivot), quicksort elements less than pivot, quicksort elements greater than pivot). Then you can read the almost-incomprehensible iterative-with-explicit-stack versions.

share|improve this answer
3  
I would not prioritize Quicksort and skip everything else. Quicksort is theoretically the fastest known sorting algorithm under ideal conditions, but under less-than-ideal conditions its performance degrades very quickly. On the other hand, if you understand mergesort and insertion sort, you can build Timsort, which is probably as close to the Holy Grail of sorting algorithms as we're ever going to get. –  Mason Wheeler Aug 15 '12 at 21:34
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.