"I'm sure some people use sorts today, but in the kind of work I do you would never explicitly call one."
Most of the applications which use them are better implemented with a database language these days. And the include the ability to sort as part of the language. The few times I needed to sort something, say ordering a list of objects of some sort, there were, at most, maybe 100 of them and a bubble sort was just fine.
These days, most of the activity in algorithms are in randomized algorithms. Most of the others that have been unsolved are at least NP hard with conventional techniques. Randomized algorithms, though, offer the hope of breaking away from NP hard or NPC traps. The problem though, is that you often can't set a hard upper bound with a randomized algorithm, at best you get a probability distribution. The big win, though, is that randomized algorithms are usually highly parallelizable. Since you don't carry a lot of state information, they are often light weight.
A good example which you might be familiar with is the Quicksort. If the pivot is selected randomly, suddenly your upper bound goes from O(n^2) to O(nlogn). That isn't usually considered to be a randomized algorithm, but it does show how randomized techniques can increase performance and simplify the algorithm. |
