Sorting

Sorting is the process of rearranging a sequence of elements into a defined order according to a comparison predicate. The elements may be numbers, strings, or records, and the sort order is typically ascending or descending; for strings, lexicographic order is common, and for composite data a key selects the value used for comparison.

Two broad categories exist: comparison-based sorts, which decide order by comparing elements, and non-comparison sorts that rely on other properties of the keys. In the usual models, comparison sorts have a lower bound of Omega(n log n) time for arbitrary inputs, and many practical algorithms achieve O(n log n) on average. Simpler sorts can be O(n^2).

Common algorithms include insertion sort, selection sort, and bubble sort (typically O(n^2) in the worst case); and more efficient sorts such as mergesort (stable, O(n log n) time, uses extra space), heapsort (in-place, O(n log n), not stable), and quicksort (in-place, average O(n log n); worst-case O(n^2) without careful pivoting). Non-comparison sorts such as counting sort, radix sort, and bucket sort run in linear time under constraints like bounded key ranges.

Stability is a property of interest: a stable sort preserves the relative order of equal elements, which matters in multi-key sorting or when maintaining input order for equal keys.

Applications include organizing data for searching, database operations, data analysis, and preparing inputs for algorithms that assume sorted data. Most programming languages provide built-in sort routines that implement one or more of these algorithms, often with options for stability and in-place operation.