PlanetMath: sorting problem

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (230)
Orphanage
Unclass'd
Unproven (519)
Corrections (17)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

sorting problem

(Algorithm)

Let $\leq$ be a total ordering on the set . Given a sequence of 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 (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.