Tieredsort seems like a good balance between performance and complexity. Enough complexity (yet still relatively simple) to get very good performance.