## You are here

Homesorting problem

## Primary tabs

# sorting problem

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

## Mathematics Subject Classification

68P10*no label found*82C35

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections