>I haven't seen anyone mention a tree sort, which is the most complex structure taught at the Community College I attended. I have no idea about its relative speed, and frankly, its been years since I've even thought about it. Indexes are much more handy.

I mentioned it, but excluded it, since it relies on building a tree first, and is more for searching, as I recall, than actual sorting...