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.