# 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\mathrm{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 |