Sort

Sorting is the process of arranging items in a collection according to a defined order. The items are typically characterized by keys that determine their order, such as numbers, strings, or dates. Common orders include numerical ascending or descending, and lexicographic order for strings. Sorting may operate on one or more keys, and can be stable (preserving the relative order of equal keys) or unstable.

Most sorting algorithms are comparison sorts, which decide order by comparing items. Among these, several achieve O(n log n) time on average, including quicksort, mergesort, and heapsort. Some simpler sorts, such as insertion sort or selection sort, have O(n^2) performance in the worst case but can be efficient for small datasets. Non-comparison sorts, such as counting sort or radix sort, can run in linear time under certain constraints on the input keys (for example a bounded range or fixed-length keys).

Implementation choices affect memory and in-place behavior. Some algorithms are in-place and require little extra storage, such as heapsort, while others like mergesort typically use additional space. Stability varies: mergesort is stable, insertion sort is stable, while many efficient in-place variants of quicksort are unstable. Practical sorting systems often use hybrid or randomized approaches to improve performance and worst-case guarantees.

Sorting underpins many computing tasks, including data organization, database query optimization, compression, and search. When data is too large to fit in memory, external sorting techniques extend sorting to disk-resident data through multi-pass algorithms.