Let $\leq$ be a total ordering on the set $S$ Given a sequence of $n$ elements, $x_1, x_2, \dots, x_n \in S$ find a sequence of distinct indices $1 \leq i_1, i_2, \dots, i_n \leq n$ such that $x_{i_1} \leq x_{i_2} \leq \dots \leq x_{i_n}$

The sorting problem is a heavily studied area of computer science, and many sorting algorithms exist to solve it. The most general algorithms depend only upon the relation $\leq$ and are called comparison-based sorts. It can be proved that the lower bound for sorting by any comparison-based sorting algorithm is $\Omega(n\log{n})$

A few other specialized sort algorithms rely on particular properties of the values of elements in $S$ (such as their structure) in order to achieve lower time complexity for sorting certain sets of elements. Examples of such a sorting algorithm are the bucket sort and the radix sort.