NIST

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.

  1. S′i ≤ S′i+1, 0 < i < N
    (the items are in order) and
  2. 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, 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.

Author: PEB

Implementation

Specific implementations can be found under the specific sort routines or at (Pascal, C++, Fortran, and Mathematica). Thomas Baudel's sort algorithm visualizer (Java) with a dozen algorithms.

More information

Demonstrations of various sorting algorithms.

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

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

Entry modified 2 September 2014.
HTML page formatted Mon Feb 2 13:10:40 2015.

Cite this as:
Paul E. Black, "sort", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 2 September 2014. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/sort.html