# 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*, *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 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