That's for comparison-based sorting algorithms (i.e. sorting objects where the only information you have about them is whether one object is "bigger"/"smaller"

That's for comparison-based sorting algorithms (i.e. sorting objects where the only information you have about them is whether one object is "bigger"/"smaller" than the other. For objects where you have more information about the object (i.e. integers) you can sort faster. My supervisor for my Master's Thesis did just that: http://www.drdobbs.com/184404062 http://www.drdobbs.com/184404062