Sorts

Sorts are categories or types into which things can be classified; in information processing, sorting refers to arranging items in a prescribed order. The concept is widely used in linguistics, taxonomy, commerce, and data processing.

In computer science, sorting is the task of rearranging a list of records so that their keys follow a defined order, such as numerical ascending or lexicographic order. A key distinction is between comparison sorts, which determine order solely by pairwise comparisons, and non-comparison sorts, which exploit numerical properties to achieve better asymptotic performance under certain conditions. Common metrics include time complexity, space complexity, and stability. A stable sort preserves the relative order of equal elements.

Classic comparison sorts include insertion sort, selection sort, bubble sort, mergesort, heapsort, and quicksort; their performances vary with input and implementation. Quicksort is typically fast on average but can degrade in the worst case; mergesort is stable and well-suited for linked structures; heapsort is in-place but not stable. Non-comparison sorts such as counting sort, radix sort, and bucket sort can be faster for integers or fixed-length keys but require constraints on the input domain.

External sorting handles data too large to fit in memory. Topological sorting orders elements of a directed acyclic graph. Partial sorts produce the smallest k elements, or a fully sorted subset. Multi-key sorts generalize to sorting by multiple fields, typically with a primary and secondary key, a topic of database queries and indexing.

Sorting is also affected by locale-specific collation, especially for strings, in databases and programming languages.