Bubble sort
In computer graphics it
is popular for its capability to detect a very small error (like swap of just
two elements) in almost-sorted arrays and fix it with just linear complexity
(2n). For example, it is used in a polygon filling algorithm, where bounding
lines are sorted by their x coordinate at a specific scan line (a line parallel
to x axis) and with increment y their order changes (two elements are
swapped) only at intersections of two lines.
Selection
Sort
Finally, selection sort
is greatly outperformed on larger arrays by Θ (n log n)
divide-and-conquer algorithms such as merge sort. However,
insertion sort or selection sort are both typically faster for small arrays
(i.e. fewer than 10–20 elements). A useful optimization in practice for the
recursive algorithms is to switch to insertion sort or selection sort for
"small enough" sub lists.
Insertion
Sort
Some divide-and-conquer algorithms such as quick sort
and merge sort
by recursively dividing the list into smaller sub lists which are then sorted.
A useful optimization in practice for these algorithms is to use insertion sort
for sorting small sub lists, where insertion sort outperforms these more
complex algorithms. The size of list for which insertion sort has the advantage
varies by environment and implementation, but is typically between eight and
twenty elements.
Merge Sort
As of Perl 5.8, merge sort is its default sorting algorithm (it was quick sort in previous versions of Perl). In Java, the Arrays sort() methods use merge sort or a tuned quick sort depending on the data types and for implementation efficiency switch to insertionsort when fewer than seven array elements are being sorted. Python uses timsort, another tuned hybrid of merge sort and insertion sort, that has become the standard sort algorithm for Java SE 7 and on the Android platform.
Utility in online
sorting
Merge sort's merge
operation is useful in online sorting, where the list to be sorted is
received a piece at a time, instead of all at the beginning. In this
application, we sort each new piece that is received using any sorting
algorithm, and then merge it into our sorted list so far using the merge operation.
However, this approach can be expensive in time and space if the received
pieces are small compared to the sorted list — a better approach in this case
is to insertelements into a binary search tree as they are received.
Quick Sort
Quick sort is a
space-optimized version of the binarytree sort. Instead of inserting items sequentially into an explicit tree, quick
sort organizes them concurrently into a tree that is implied by the recursive
calls. The algorithms make exactly the same comparisons, but in a different
order. An often desirable property of a sorting algorithm is stability - that is the order of elements that compare equal
is not changed, allowing controlling order of multikey tables (e.g. directory
or folder listings) in a natural way. Quick sort also competes with merge sort,
another recursive sort algorithm but with the benefit of worst-case O (n
log n) running time. Merge sort is a stable sort,
unlike standard in-place quick sort and heap sort, and can be easily adapted to
operate on linked lists and very large lists stored on
slow-to-access media such as disk storage or network attached storage. Like merge sort,
quick sort can be implemented as an in-place stable sort, but
this is seldom done. Although quick sort can be written to operate on linked
lists, it will often suffer from poor pivot choices without random access. The
main disadvantage of merge sort is that, when operating on arrays, efficient
implementations require O (n) auxiliary space, whereas the
variant of quick sort with in-place partitioning and tail recursion uses only O
(log n) space. (Note that when operating on linked lists, merge sort
only requires a small, constant amount of auxiliary storage.)
Radix Sort
Note that this
recursive sorting algorithm has particular application to parallel computing, as each of the bins can be
sorted independently. In this case, each bin is passed to the next available
processor. A single processor would be used at the start (the most significant
digit). Then, by the second or third digit, all available processors would
likely be engaged. Ideally, as each subdivision is fully sorted, fewer and
fewer processors would be utilized. In the worst case, all of the keys will be
identical or nearly identical to each other, with the result that there will be
little to no advantage to using parallel computing to sort the keys.
In the top level of
recursion, opportunity for parallelism is in the Countingsort portion of the algorithm. Counting is highly parallel, amenable to the
parallel_reduce pattern, and splits the work well across multiple cores until
reaching memory bandwidth limit. This portion of the algorithm has
data-independent parallelism. Processing each bin in subsequent recursion
levels is data-dependent, however. For example, if all keys were of the same
value, then there would be only a single bin with any elements in it, and no
parallelism would be available. For random inputs all bins would be near
equally populated and a large amount of parallelism opportunity would be
available.
Note that there are
faster sorting algorithms available, for example optimal complexity O(log(n))
are those of the Three Hungarians and Richard Cole and Batcher's bitonic
merge sort has an algorithmic complexity of O(log2(n)), all
of which have a lower algorithmic time complexity to radix sort on a CREW-PRAM. The fastest known PRAM sorts were described in 1991 by
David Powers with a parallelized quick sort that can operate in O(log(n)) time
on a CRCW-PRAM with n processors by
performing partitioning implicitly, as well as a radix sort that operates using
the same trick in O(k), where k is the maximum key length.
However, neither the PRAM architecture or a single
sequential processor can actually be built in a way that will scale without the
number of constant fanout
gate delays per cycle increasing as O(log(n)), so that in effect a
pipelined version of Batcher's bitonic merge sort and the O(log(n)) PRAM sorts are all O(log2(n))
in terms of clock cycles, with Powers acknowledging that Batcher's would have
lower constant in terms of gate delays than his Parallel Quick sort
and Radix sort, or Cole's Merge sort, for a key length-independent sorting
network of O(nlog2(n))
Heap Sort
Heap sort primarily
competes with quicksort, another very efficient general purpose nearly-in-place
comparison-based sort algorithm.
Quick sort is typically
somewhat faster, due to better cache behavior and other factors, but the
worst-case running time for quick sort is O (n2),
which is unacceptable for large data sets and can be deliberately triggered
given enough knowledge of the implementation, creating a security risk. See quick sort
for a detailed discussion of this problem, and possible solutions.
Thus, because of the O(n
log n) upper bound on heap sort’s running time and constant upper bound
on its auxiliary storage, embedded systems with real-time constraints or
systems concerned with security often use heap sort.
Heap sort also competes
with mergesort, which has the same time bounds, but requires Ω (n) auxiliary space,
whereas heap sort requires only a constant amount. Heap sort also typically
runs more quickly in practice on machines with small or slow data caches.
On the other hand, merge sort has several advantages over heap sort:
- Like quick sort, merge sort on arrays has considerably better data cache performance, often outperforming heap sort on a modern desktop PC, because it accesses the elements in order.
- Merge sort is a stable sort.
- Merge sort parallelizes better; the most trivial way of parallelizing merge sort achieves close to linear speedup, while there is no obvious way to parallelize heap sort at all.
- Merge sort can be easily adapted to operate on linked lists (with O(1) extra space) and very large lists stored on slow-to-access media such as disk storage or network attached storage. Heap sort relies strongly on random access, and its poor locality of reference makes it very slow on media with long access times. (Note: Heap sort can also be applied to doubly linked lists with only O(1) extra space overhead)
Intro Sort
Is an interesting
alternative to heap sort that combines quick sort and heap sort to retain
advantages of both: worst case speed of heap sort and average speed of quick sort?
