For small arrays, the next three classic sorting algorithm suffice.
The complexity does not depend on the initial placement of the data. It's quite appropriate only for small n as O(n^2) grows rapidly. In contrast of a O(n^2) comparisons, it requires only O(n) data moves. Thus,
selection sortcould be a good choice over other counterparts when data moves are costly but comparisons are not.
The number of loops depends on the initial placement of the data, which means the sorting will be terminated when no exchages are done during one pass.
insertion sortalgorithm is O(n^2) in the worst case. For small arrays, the simplicity makes it an appropriate choice. For large arrays,
insertion sortcan be prohibitively inefficient unless the array is already sorted, in which case, the sort is O(n).
For extremely large arrays, faster sorting algorithms are needed.
As one of the two most important devide-and-conquer sorting algorithm,
merge sortworks in elegant recursive manners. Besides, it’s also readily extended to external sorting. Oblivious to initial placement of data,
merge sortalways gives the same performance. The complexity is O(nlogn), which is significantly faster than O(n^2). Despite extremely efficient with respect to time, the
merge sortrequires an auxiliary array. This extra storage and the necessary copying are disadvantages.
Quick Sortperforms better when the array can be halved for each round. Thus, the complexity is O(nlog(n)), which is the best case. For the worst case, the complexity is O(n^2). The average behaviour of
Quick Sortis O(nlog(n)) as well. We have shown that the
Merge Sortis alwasy O(nlog(n)), the
Quick Sortis faster in practice and doesn’t require an auxillary array for merging. If the data is sufficiently “random”,
Quick Sortperforms no worse than any known comparison-based sorting algorithms. While the worst-case behaviour of
Merge Sortis of the same order of magnitude as a quick sort’s average-case behaviour, in most situations
Quick Sortwill run definitely faster than
Merge Sort. However, the
Quick Sortis significantly slower than the
Merge Sortfor worst case.