A sorting algorithm rearranges a sequence so that its elements follow a chosen ordering relation.

In comparison sorting, the algorithm learns order only by comparing pairs of elements. Different comparison sorts can have the same asymptotic complexity while differing in useful properties.

A sort is stable when elements that compare equal keep their original relative order. Stability matters when records are sorted successively by several keys.

An in-place sort uses only a small amount of auxiliary storage beyond the input, while other algorithms trade additional memory for simpler or faster operations.

Comparison sorting is a model: algorithms may also exploit extra structure in the keys, such as bounded integers or digits, rather than learning order only through pairwise comparisons.