Gargravarr wrote:jc wrote:Some years back, perhaps in the 1980s, there was a competition for the "worst" sort algorithm. ...
Please let us know if you remember the winner.
The worst one I've ever used in production code is BubbleSort. Because the boss liked it for some obcure reason.
Maybe I'll try to find it.
I've had a few situations where BubbleSort was actually the fastest of the sorts we tested. The explanation is that sorts are conventionally judged solely on their speed at sorting randomly-ordered data. But in the real world, some kinds of data start out with some internal order. If that's close to the desired order, bubbling a list can be a very fast way of sorting it.
One common example is data being collected from a lot of other sites, with varying transit times to the central data site. If you want them sorted by send time, they're almost in that order, with few items out of place by more than a few slots. If you have millions of items, QuickSort can be horribly slow, while BubbleSort will quickly in O(N) time undo the jitter caused by network transit time. Your main problem then is keeping all the senders' clocks in sync ...
In the Real World (TM), it's often foolish to look for the best sort routine. Rather, you need a collection of sort routines, plus testing to discover which (if any) is best for your actual data sets. Sometimes you're surprised when a "bad" sort algorithm turns out to be consistently the fastest for one of your sources of data. This is generally because the data had a certain amount of order, and one sort algorithm happened to take advantage of the order that existed. But the documentation rarely tells you what kinds of data it sorts the fastest.
I've also seen teams go through long, rancorous discussions of the best sort algorithm for their data, when it turns out their lists are typically under 100 items, and all the routines finish so fast that their clock can't even measure the differences.