![[HomePage]](https://nostalgia.wikipedia.org/static/images/project-logos/nostalgiawiki.png)
A sort algorithm is an algorithm that puts elements of a list into order. Efficient sorting is important to optimizing the use of other algorithms (such as search algorithms and merge algorithms) that require sorted lists to work correctly; it is also often useful for canonicalizing data and for producing human-readable output.
Many common sort algorithms are used in computer science. They are often classified by:
- computational complexity (worst, average and best-case behaviour) in terms of the size of the list (n). Typically, good behaviour is O(n log n) and bad behaviour is O(n2). Sort algorithms which only use an abstract key comparison operation always need at least O(n log n) comparisons on average; sort algorithms which exploit the structure of the key space cannot sort faster than O(kn) where k is the average key length.
- memory usage (and use of other computer resources)
- stability: a sort algorithm is stable if, whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appear before S in the sorted list. (Unstable sort algorithms can usually be made artificially stable by adding an extra number to the key defining the position in the original list.)
Some sorting algorithms follow:
| Name | Worst case complexity | Average case complexity | Best case complexity | Average case memory usage | Stable? |
|---|---|---|---|---|---|
| Bubble sort | O(n2) | O(n2) | O(n) - already-sorted data | works in-place | Yes |
| Straight insertion sort | O(n2) | O(n2) | O(n) - already-sorted data | works in-place | Yes |
| Bucket sort | . | . | . | . | . |
| Counting sort | O(n) | . | . | Varies with data | N/A |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | works in-place | no |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) extra space | Yes |
| Quicksort | O(n2) - already sorted data | O(n log n) | O(n log n) | works in-place, needs O(log n) auxiliary storage | No |
| binary tree sort | O(n2) -- already sorted data | O(n log n) | O(n log n) | O(n), typically several pointers per input item | Yes |
| Pigeonhole sort | O(n) | . | . | . | . |
| Radix sort (k = keyspace size) |
O(n log k) | O(n log k) | O(n log k) | O(n) extra space | Yes |
| Shell sort (decreasing gap insertion sort) |
O(n1.5) | O(n1.25) | O(n log n) - already-sorted data | works in-place | No |
References
D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching.
http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/algoen.htm has analyses of many of these algorithms.
Ricardo Baeza-Yates has many sorting algorithms on the Web at http://www.dcc.uchile.cl/~rbaeza/handbook/sort_a.html