Sort 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(n²). 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