Comparison of Sorting Algorithms

Naive algorithms have an unfortunate name due to the emotional connotations of the word "naive". A naive algorithm is simply the first algorithm known to be correct which doesn't fall into one of the other categories.

Before an algorithm is known to be correct (that is, to provide the correct results), concern about its execution speed is irrelevant ^[1]. After at least one algorithm is known to be correct the primary concern is generally speed. These facts conspire to ensure the first correct algorithm is almost always the slowest known algorithm.

A divide-and-conquer algorithm breaks the problem into two or more subproblems. The subproblems do not need to be equally sized, but the total number of (levels of) iteration of the algorithm should be proportional to log(n) instead of n.

This property holds whenever the size of each subproblem is proportional to the size of the problem. If the size of one subproblem is fixed and the other subproblem is whatever is left over the number of (levels of) iteration of the algorithm is proportional to n.

Finally, implementations of divide-and-conquer algorithms generally switch to a different algorithm for small enough problems where those algorithms are more efficient.

An invariant property algorithm is based on the fact that objects with invariant properties (e.g., the heap of the heap sort) are often efficiently modified a single element at a time.

The heap sort is a classic example of this. Given a heap, it takes time O(lg (n)) to insert (remove) an item to(from) the heap. It is easy to prove that the worst case performance of the heap sort is O(n lg (n)), the best of these algorithms (although quick sort can match it with a well-chosen pivot selection algorithm).

As an aside, divide-and-conquer algorithms often exploit invariant properties as well. The distinction is that an algorithm such as heap sort doesn't have a divide-and-conquer aspect to it.

A meta-algorithm is an algorithm which uses another algorithm efficiently. This often results in pronounced performance improvements since the meta-algorithm can often guarantee tighter restrictions on the characteristics of the data passed to the subordinate algorithm, allowing the use of more efficient but less general algorithms than could be used without the intermediatary behavior of the meta-algorithm.

The Shell sort is a meta-algorithm since it guarantees that the subordinate algorithm will see arrays which are either extremely small or already nearly sorted.