Sort algorithm

In computer science and mathematics, a sort algorithm is an algorithm that puts elements of a list into order by means of a certain ordering, often lexicographical. 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.

Sort algorithms used in computer science are often classified by:

• computational complexity (worst, average and best 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(n log k) where k is the size of the keyspace.
• memory usage (and use of other computer resources)
• stability: stable sorts keep the relative order of elements that have an equal key. That is, 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.)

Sorting algorithms that are not stable can be specially implemented to be stable. One way of doing this is to artificially extend the key comparison, such that comparisons between two objects with otherwise equal keys are decided using the order of the entries in the original data order as a tie-breaker.

Some sorting algorithms follow with runtime order

• Bubble sort - O(n²)
• Cocktail sort (bidirectional bubble sort) - O(n²)
• Comb sort * - O(n log n)
• Selection sort * - O(n²)
• Insertion sort - O(n²)
• Bucket sort - O(n); requires O(n) extra memory
• Counting sort - O(n+k); requires O(n+k) extra memory
• Heapsort * - O(n log n)
• Smoothsort * - O(n log n)
• Merge sort - O(n log n)
• Quicksort * - O(n log n), O(n²) worst case
• Binary tree sort - O(n log n); requires O(n) extra memory
• Pigeonhole sort - O(n+k); requires O(k) extra memory
• Radix sort - O(nk); requires O(n) extra space
• Shell sort - O(n^1.25)

Questionable sort algorithms not intended for production use:

• Bogosort * - O((n/2)!); requires O(n) extra space

(*) unstable

See work-in-place article for the list of sort algorithms that can be written as work-in-place.

An old version of QBASIC has a file "sortdemo.bas" in the examples folder that provides a graphical representation of several of the various sort procedures described here, as well as performance ratings of each.

Compare with:

• sorting networks

External links and 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.
• http://www.aeriesoft.ru/Projects/SortAlg/ has information on 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
• For a 'Dictionary of Algorithms, Data Structures, and Problems' go to http://www.nist.gov/dads/
• For some slides and pdf's see Manchester university's course notes: http://www.cs.man.ac.uk/~graham/cs2011.html
• For a repository of algorithms with source code and lectures, see The Stony Brook Algorithm Repository at http://www.cs.sunysb.edu/~algorith/