Sorts of O(n2) usually have two nested loops inside their
algorithm, with the indexes walking up or down at least part of the array in
each loop.
O(n2) sorts are significantly slower than the O(n
lg(n) )
sorts, but they are useful small amounts of data because their algorithms are
very simple to implement.
Demonstration and analysis of Bubble Sort. Bubble Sort
is the slowest, but in its short circuit version it can be quite useful for
certain types of data, particularly data that is already partially sorted.
Demonstration and analysis of Selection Sort. It is
about 4 times faster than Bubble Sort, but there is no way to short circuit it,
so for certain types of data it is much slower than Bubble sort. It takes
about the same amount of time no matter what the data is.
Demonstration and analysis of Insertion Sort. Also
about 4 times faster than Bubble Sort, it also can not be short circuited.
It does, however, do well with partially sorted data, still usually beating
Bubble Sort.
O(n lg(n)) Sorts
Sorts of O( n lg(n) ) use a divide and conquer
strategy. They tend to divide the size of the sort into halves, then
fourths, then eighths, then sixteenths, etc.
Demonstration and analysis of the Quick Sort.
The Quick Sort algorithm calls itself recursively twice,
hopefully dividing the current array into two approximate halves.
Since the two recursive calls can be sent unequal parts of
the array, in the worst case the recursion is called n - 1 times and the Quick
Sorts degenerates to O(n2). Usually there is a stack overflow before the
sort is finished.
For totally random data, however, the Quick Sort is usually
the fastest standard sort.
There are a number of variations on Quick Sort. Quick
Sort is more efficient if the recursion is stopped early and the remaining data
in each small portion is sorted by Bubble or Insertion Sort.
Demonstration and analysis of Shell Sort.
The Shell Sort algorithm uses two nested loops, but the index
numbers are divided each time in the outer loop, instead of walking the entire
array.
Shell Sort achieves O( n lg(n) ) times, although this cannot
be proven mathematically. It is obvious from empirical studies, however.
Shell Sort is about twice to four times as long as Quick Sort
for most data, but it is highly stable and can be used on any data.
Demonstration and analysis of Merge Sort.
The Merge Sort algorithm is recursive, similar to Quick Sort,
but much less complex.
Since the Merge Sort algorithm simply calculates the halfway
point, instead of guessing as the Quick Sort does, it is usable with all kinds
of data. It does not degenerate to O(n2) with certain types of data.
Merge Sort requires twice the memory of the Quick or Shell
sorts, which can be done in-place.
Merge Sort often beats Quick Sort, and is often used if the
memory is available.
There is an in-place Merge Sort algorithm, but it is much
less efficient.