Bubble Sort Selection Sort Shaker Sort Insert Sort Quick Sort
Number of comparisons
The number of comparisons is often the driving factor in the 'slowness' of an algorithm. Indeed, a comparison can involve much more computation than the base loop of the sort algorithm: for instance, when sorting almost identical strings, one can have to compare character for character on large lengths before decising which string comes first. Sometimes, while pointers to the objects are stored in memory and thus cheap to move, the actual data must be kept on remote storage, and loaded for comparisons purposes. In this later situation, studying the best strategy becomes even more complex, as one can consider caching a few sort keys in memory: this means that a good algorithm may not try to reduce the number of comparisons, but rather increase the locality of references, reusing cached data as much as it can before advancing further.
Still, one often considers the number of comparisons as the best mean to compare sort algorithms. But it is not sufficient: By this rating, dichotomic insertion would show the best algorithm, and it is almost never the case.
It is easy to show that a sort algorithm based on comparison and not using additional storage has to do at least log2 n! comparisons in the worst case. One often translates this constraint in approximating the number of comparisons by n log n.
Number of exchanges
Any algorithm has to do at least n moves in the worst case. Yet, naive
approaches are
quadratic in number of exchanges. The best algorithm for number of
exchanges is selection sort, quicksort coming fairly close.
Stack and additional costs
Modern algorithms like quicksort and in place stable sort hide some memory costs to their apparent efficiency: Both require a stack to remember the sub arrays that need to be sorted or merged. In the case of quicksort, this stack can grow in the worst case to be proportional to log(size of the array), which makes it unfair to call quicksort a true 'in place' sort.
Conclusion
A good sorting algorithm must balance complexity in number of comparisons,
number of exchanges, being at most comparable to n log n in number of comparisons
and linear in number of exchanges. Stack costs should be considered too.
While quicksort is the most commonly used sort, one can consider simpler
and more efficient algorithms, if one has a good hint of the distribution
of the data to sort.