 # 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.

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.