Sorting algorithm
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). A sort algorithm cannot do better than O(n).
- 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 |
| 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 lg n) | O(n lg n) | O(n lg n) | works in-place | no |
| Merge sort | O(n lg n) | O(n lg n) | O(n lg 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 lg n) | O(n lg n) | O(n), typically several pointers per input item | Yes |
| Radix sort | . | . | . | . | . |
| Shell sort | . | . | . | . | . |
/Talk
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