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

 Title sorting problem Canonical name SortingProblem Date of creation 2013-03-22 11:43:37 Last modified on 2013-03-22 11:43:37 Owner Logan (6) Last modified by Logan (6) Numerical id 10 Author Logan (6) Entry type Algorithm Classification msc 68P10 Classification msc 82C35 Related topic TotalOrder Related topic PartialOrder Related topic Relation Related topic Heapsort Related topic Bubblesort Related topic BinarySearch Related topic InPlaceSortingAlgorithm Related topic InsertionSort Related topic LandauNotation Related topic Quicksort Related topic SelectionSort