Definition: Arrange items in a predetermined order. There are dozens of algorithms, the choice of which depends on factors such as the number of items relative to working memory, knowledge of the orderliness of the items or the range of the keys, the cost of comparing keys vs. the cost of moving items, etc. Most algorithms can be implemented as an in-place sort, and many can be implemented so they are stable, too.
Formal Definition: The sort operation may be defined in terms of an initial array, S, of N items and a final array, S′, as follows.
Generalization (I am a kind of ...)
Specialization (... is a kind of me.)
quicksort, heapsort, Shell sort, comb sort, radix sort, bucket sort, insertion sort, selection sort, merge sort, counting sort, histogram sort, strand sort, J sort, shuffle sort, American flag sort, gnome sort, bubble sort, bidirectional bubble sort, treesort (1), adaptive heap sort, multikey Quicksort, topological sort.
See also external sort, internal sort, comparison sort, distribution sort, easy split, hard merge, hard split, easy merge, derangement.
Note: Any sorting algorithm can be made stable by appending the original position to the key. When otherwise-equal keys are compared, the positions "break the tie" and the original order is maintained.
Knuth notes [Knuth98, 3:1, Chap. 5] that this operation might be called "order". In standard English, "to sort" means to arrange by kind or to classify. The term "sort" came to be used in Computer Science because the earliest automated ordering procedures used punched card machines, which classified cards by their holes, to implement radix sort.
Demonstrations of various sorting algorithms.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 24 August 2009.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Paul E. Black, "sort", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 24 August 2009. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/sort.html