Most programming language standard libraries come equipped with one or more built-in sort routines these days. Most of the time, that's what you want.
"Library sort" algorithms tend to use a combination of basic sort algorithms that you've seen in class, and tune themselves either at compile time or at run time.
That's why, for example, the standard library sort in C++ might use merge sort on linked lists and quick sort on arrays. And a typical industrial-strength quick sort implementation will revert to insertion sort on small intervals, or heap sort if the partitioning strategy seems to be going awry.
Most library sorts are comparison-based because of external constraints. They must work on user-defined data types, for example, and it's typically much easier for the user of such a sort algorithm to supply a comparison operation than, say, a radix extraction operation. Moreover, users often want to sort on secondary keys if primary keys are equal (e.g. surname then first name). It's much easier to express this in terms of comparison rather than some other formulation.
I've been in the business a long time, and there's really only a few times I can think of where writing my own sort was the best option. Two examples that are easy to explain:
First example: I wrote the sort subsystem for a database server. It me about six months. As with library sorts, it used a combination of sort algorithms and adjusted its behaviour depending on what situation it found itself in. Sorting database records is an interesting case because accessing the sort key is sometimes the most expensive operation; disk seeks are one of the most expensive things there is, especially if the disk is network-attached.
The main idea which cracked this problem was to use the fact that users almost always wanted to sort on multiple keys. So I used partitioning sort algorithms which discovered "ranges" where the primary sort key was the same. Secondary keys are only needed to resolve those ranges. Many sort algorithms (e.g. ternary quick sort, radix sort) can be adapted to return ranges.
Second example: I wrote some firmware which needed to read about 1000 values from a hardware device, and then do quantile extraction. The complication is that the microcontroller that this ran on had essentially no extra read-write memory available, so algorithms like radix sort or quick sort were not an option. I used Shell sort, which was by far the best tradeoff.
There's a bunch of special-case information that everyone who has worked with sorting knows, such as "bubble sort is always worse than insertion sort", and "heap sort has terrible constant factors; last resort only". But this general advice is probably all you need to know:
- The best sort algorithm is the one that fits the peculiarities of your data and your platform.
- The second-best sort algorithm is one you didn't have to write.
- Make sure that sort is a bottleneck before getting fancy.
Knowing lots of sort algorithms is good for you, but not necessarily to the point where you can implement them from memory. Knowing that there is a tradeoff is more valuable knowledge than what the tradeoffs actually are. Then, when you come across one of those few times where you need to write your own sort, you'll know where to look.
