sort

(algorithm)

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.

S′_i ≤ S′_i+1, 0 < i < N
(the items are in order) and
S′ is a permutation of S.

Generalization (I am a kind of ...)
permutation.

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.

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.

Author: PEB

Implementation

Specific implementations can be found under the specific sort routines or at (Pascal, C++, Fortran, and Mathematica).

More information

Demonstrations of various sorting algorithms; Links to different sorting algorithms. Jim Gray's latest records of items sorted per penny, items sorted in a minute, and time to sort a terabyte.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified Wed Dec 14 16:50:33 2005.
HTML page formatted Thu Dec 15 09:30:43 2005.

Cite this as:
Paul E. Black, "sort", from Dictionary of Algorithms and Data Structures, Paul E. Black, ed., NIST.
http://www.nist.gov/dads/HTML/sort.html