Sorting is the rearrangement of numbers (or other orderable objects) in a list into their correct lexicographic order. Alphabetization is therefore a form of sorting. Because of the extreme importance of sorting in almost all computer algorithms and database applications, a great deal of effort has been expended in the creation and analysis of efficient sorting algorithms. A number of common sorting algorithms include heapsort, merge sort, quicksort, selection sort, and shellsort.

The following table summarizes the number of comparisons or elementary operations used by several comparison sorts, which determine order by comparing pairs of items, on items. The bounds suppress constant factors and lower-order terms. The base of the logarithm is immaterial in these big-O bounds because changing the base multiplies the logarithm by a constant. Quicksort's quadratic worst case can be avoided with suitable randomization or pivot safeguards, while shellsort bounds depend on the chosen gap sequence.

For distinct keys, a correct comparison sorter must distinguish all possible total orders. The resulting worst-case lower bound on the depth of the binary tree of comparisons is , where denotes the ceiling function (Knuth 1998).

Nash (2026a) reports a deterministic online adversary that is initialized using only and keeps its answers jointly consistent with some total order. It uses a fixed polynomial number of bit operations per query and forces every correct comparison sorter on distinct keys to make comparisons as . Nash attributes the adversary and its analysis to GPT-6 Astra and reports human review of the main text. The appendices are identified as AI-generated and excluded from that review. The continuous-position argument is accompanied by finite checks of selected identities. The Lean development for the earlier integer-color construction verifies the asymptotic guarantee and a polynomial cost bound in an explicit bit-work model (Nash 2026b). A separate public branch formalizes the continuous adversary's consistency, asymptotic comparison bound, and polynomial initialization and query costs in an explicit arithmetic cost model (Nash 2026c). Its reported continuous integration checks include a build, kernel replay with leanchecker, and an audit admitting only Lean's standard logical axioms. These are formal cost charges rather than a timing bound for executing the Lean implementation.

See also

Heapsort, Merge Sort, Ordering, Quicksort, Selection Sort, Shellsort, Sort-Then-Add Sequence, Weighing

Explore with Wolfram|Alpha

References

Knuth, D. E. The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed. Reading, MA: Addison-Wesley, 1998.Nash, N. "An Optimal Deterministic Adversary for Sorting." Revised manuscript. 2026a. https://github.com/nicknash/sorting-adversary-proofs/blob/8dbe152e8859af86d78569e427f57ce79f6fc120/for-humans/output/pdf/paper.pdf. Initial deposit: https://hexagonmath.org/2611.00196v1.Nash, N. "Sorting Adversaries in Lean." 2026b. https://github.com/nicknash/sorting-adversary-proofs/blob/d376e17acd4b9b351f43356ccd274e807339c120/docs/optimal-adversary-formalization.md.Nash, N. "Continuous Adversary Formalization." 2026c. https://github.com/nicknash/sorting-adversary-proofs/blob/68ba6a2073abb8ea661d5347a3fee06c120c5a64/docs/continuous-adversary-formalization.md.National Institute of Standards and Technology. "Sort." https://xlinux.nist.gov/dads/HTML/sort.html.Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. "Sorting." Ch. 8 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 320-339, 1992.Skiena, S. "Sorting and Searching." §1.1.6 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 14-16, 1990.

Referenced on Wolfram|Alpha

Sorting

Cite this as:

Weisstein, Eric W. "Sorting." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Sorting.html

Subject classifications