Sort algorithm

From Wikipedia

HomePage | Recent changes | View source | Discuss this page | Page history | Log in |

Printable version | Disclaimers | Privacy policy

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

/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