sorting problem

Let $\le$ be a total ordering on the set $S$. Given a sequence of $n$ elements, $x_1,x_2,\mathrm{\dots },x_n\in S$, find a sequence of distinct indices $1\le i_1,i_2,\mathrm{\dots },i_n\le n$ such that $x_{i_1}\le x_{i_2}\le \mathrm{\dots }\le 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 $\le$, and are called comparison-based sorts. It can be proved that the lower bound for sorting by any comparison-based sorting algorithm is $\mathrm{\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