Caltrops - Xenosaga - My observations of sorts

Forum Overview :: Xenosaga

by Ray of Light 11/22/2005, 12:40pm PST

I was disappointed to see your post fail to deliver on the promise of its author field. Just in case I'm not the only one, I will do what you lack the will to, and provide a breakdown of the sorting scene:

Bubble: this is the sort you start out with, and you should look to replace it as soon as possible. Some people will keep it around for small jobs, but the risk of unexpected data growth creates massive liabilities. Just say no.

Quick: the mainstay of most sorting arsenals, and it's hard to beat the versatility: it can invert, it can tidy, it's stable and it's almost always fast. Still, you can catch a lot of donks out when they expect their shiny toy to do all the work for them. One minute, he's flashing a textbook implementation around like he's cock of the walk; next minute, look, there's an ordering tailored to his naïve partitioning heuristic and BAM! it's Welcome Wagon time in Quadratic-Runtime Town. Or better yet, he'll mate the sort with a data structure or storage medium that can't pay the heavy insertion toll and all I have to do is sit back and laugh while the cumulative insertion time bleeds him out. Economizing on comparisons only gets you halfway, folks.

Radix: I call this one the "troll-sort:" some noob will reinvent it and claim to have discovered general-purpose sorting in linear time. There's nothing more satisfying than mentioning the runtime costs imposed by radices of arbitrary size, and then picturing the gobsmacked look on his or her stupid face. Still, it was built to take down big lists of phone numbers and is unmatched in this regard. Don't pass up a chance to see it at work against one of those, doing the thing it does best.

Selection / Insertion: I group them under the banner of "sorts I can code without looking them up". A lot of people ignore them because they are slow, but I still like to bring them in sometimes. If your quicksort is going to get mired, it will be on the tail-end, so let your heavies break the entropic back of an unordered set, then go oldschool to mop up.

Heap & Merge: I'll cover these in a later installment, "The Exotics".