Let be a total ordering on the set .
Given a sequence of elements, , find a sequence
of distinct indices such that .
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 , and are called comparison-based sorts. It can be proved that the lower bound for sorting by any comparison-based sorting algorithm is .
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.
|Date of creation||2013-03-22 11:43:37|
|Last modified on||2013-03-22 11:43:37|
|Last modified by||Logan (6)|