So i know there are more than a dozen sorting algorithms out there. I understand some are better than others, but i don't get why there's not one agreed "best" sorting alg. out there. Does it have to do with the order? Which are the fundamentally best ones?
The best algorithm may change depending on your constraints and the input. You could argue that quicksort is best based on its O(n lg n) average running time. It is usually taught early on in CS programs as an example of a fast sorting algorithm. However, for small values of n you're actually better off using a sorting algorithm with worse asymptotic performance that is better suited to your hardware. Good cache coherency can make a big difference and asymptotic running times can hide some pretty big constants. Quicksort also performs badly on sorted or nearly sorted lists. In these cases you end up hitting quicksort's worst case performance of O(n^2).<p>You might have other constraints on your sorting algorithm. What if you wanted to sort twice and have ties in the second sort broken by the results of the first sort? You'd need to pick a stable sorting algorithm for your second sort. Someone else already mentioned in place sorting. If you have lots of items to sort but they are all relatively short you might find that a radix sort is fastest. You might not even really need to sort your items. If you just need to always be able to get the smallest or largest you could store your values in a heap.<p>To sum up, the best sorting algorithm will depend on your hardware, your data, and how you're planning to use it.
"Why are there many sorting algorithms?" could be understood as a very deep ontological question. It is a <i>fundamental</i> fact that there are many different algorithms that can be used to sort a list, and each of those ways has some <i>fundamental</i> trade-offs.<p>Nonetheless, only a handful of those approaches are typically used in production systems, so the question could be understood instead as "Why don't we just all use some heavily optimized variant of quicksort, and forget about the rest?" One good reason (in addition to the others mentioned) is that sorting algorithms are almost the perfect teaching tool.<p>There are a wide variety of approaches. Most of them are almost trivially simple to understand, and many can serve as strong illustrative examples of particular theoretical concepts.<p>For example, sorting algorithms are a great way to demonstrate why divide and conquer approaches (like quicksort or mergesort) tend to result in `n*log(n)` time complexity, while iterative algorithms (like bubble or insertion) tend to be polynomial. Another example, studying the symmetrical relationship between quicksort and mergesort can be very revealing to the cause of the tradeoffs of each.
There are trade-offs.<p>Can you use extra memory, or do you require an in-place sort?<p>Does your data even fit in ram, or will you be continually reading from and writing to disk? (Alternatively: does your data fit in L1 cache, or will you be continually reading from and writing to slower parts of memory?)<p>Do you need a stable sort? It'll be slower.<p>Do you want the sort that's faster on average? Or the one that has the fastest worst case?
Adding to what mooism said, there is a general "consensus" of sorts as to which sorting algorithm is "best". "Best" in this case would be fast enough for most general purpose computing.<p>The answer is: Timsort. It's a combination of mergesort and some kind of insertion sort. It's currently used in the default sorting libs of Java, Python, Android, Octave.. blabla.<p>But there WILL come a time where you need to write your own sorting algo(or use a different algo from a different lib). This is where you need to know your sorting algos and their times/memories tradeoff
Because in order to decide which is best, you need some criteria for success. You also need to consider the application and hardware.<p>E.g. if sorting 16-bit or smaller integers, the best algorithm is to build a histogram in a single pass, then expand it again. That's assuming PC/laptop/smartphone hardware, if you are programming a microcontroller you may not have enough memory available.<p>Some applications want sorting to be a one-shot deal. Other applications want a dynamic data structure that maintains sorted order -- this is the binary tree. If the things you are sorting are very large and hence stored on disk instead of in memory, you may remember that disk hardware must fetch a whole sector to fetch one byte, having larger tree nodes can be a win because you gain when it makes the tree flatter, but the loss you pay doesn't matter because when reading a anything from the disk, you get the whole sector it's in for no additional cost. These are called B-trees and are very popular in database implementations.<p>If your hardware architecture demands the indices of the things you're comparing must be fixed (i.e. you're not allowed to use the data to decide which array slots need to be compared), you want a sorting network. This applies to designing sorting hardware, and is also used in programming sorts on GPU's.<p>At least one other poster's noted that caches on modern hardware give mergesort a strong advantage over quicksort.
The appropriateness of various sorts has changed overtime, arguably quicksort is not particlary good on modern hardware (caches and prefetch wise) due to its poor locality properties, but if you switch to a simpler chip with low ram, then prehaps quicksort could be a contender again..<p>The tradeoffs of the various sorts around, can matter depending on the context of your problem and platform
In addition to what others have said, there's some amount of ego for the respective inventors and colleagues of inventors of sorting algorithms. So some professors harp on certain algos only because their former grad student invented it.<p>And, yeah, it all depends on the context for your sort. Bubble sort (!) can be good if you know only one element is out of order.